數字三角形+字母塔+字母表+Matrix+ Jumping Frog（跳蛙）+求兩圓相交的面積+看電影+谷歌的招聘+漢諾塔問題+運算式求值
7-1 數字三角形 (10分)
觀察下面的數字金字塔，寫一個程式查找從最高點到底部任意處結束的路徑，使路徑經過數字的和最大，每一步可以從當前點走到左下方的點也可以到達右下方的點，
在上面的樣例中,從13到8到26到15到24的路徑產生了最大的和86，
輸入格式:
第一個行包含R(1≤ R≤1000)，表示行的數目，
后面每行為這個數字金字塔特定行包含的整數，
所有的被供應的整數是非負的且不大于100，
輸出格式:
單獨的一行，包含那個可能得到的最大的和，
輸入樣例:
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
輸出樣例:
86
題解：
#include<iostream>
using namespace std;
int a[1001][1001];//存放數塔
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)cin>>a[i][j];
}
for(int i=n-1;i>=1;i--)
{
for(int j=1;j<=i;j++)
{
a[i][j]+=max(a[i+1][j],a[i+1][j+1]);//自底向上找最大值更新數塔
}
}
cout<<a[1][1];
return 0;
}
7-2 字母塔 (10分)
請撰寫程式，顯示字母塔，
輸入格式
高度(不超過 26 的正整數)
輸出格式
顯示指定高度的字母塔
輸入樣例
5
輸出樣例
A
ABA
ABCBA
ABCDCBA
ABCDEDCBA
題解：
//其實很簡單，多試幾次就好了
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
char x='A';
for(int j=n-i;j>0;j--)cout<<" ";
for(int j=1;j<=i;j++)
{
cout<<x;
x=x+1;
}
x=x-1;
for(int j=1;j<i;j++)
{
x=x-1;
cout<<x;
}
cout<<endl;
}
}
7-3 字母表 (10分)
我們定義一個小寫字串是“按字母表的”，當且僅當它洗掉掉一些字符后，可以變為”abcdefghijklmnopqrstuvwxyz”， 給定一個長度為n的小寫字母字串，至少插入多少個字符才能使其變成“按字母表的”，
輸入格式:
輸入第一行為一個整數T（1<=T<=100），代表測驗資料的組數，隨后T行，每行都是由小寫字母’a’-'z’組成的一串字符s (1=<|n|<=50)，
輸出格式:
輸出為了讓s變成“按字母表的”，至少要插入的字符個數，每組輸出占一行，
輸入樣例:
2
xyzabcdefghijklmnopqrstuvw
aiemckgobjfndlhp
輸出樣例:
3
20
題解（軍軍）：
//當作最長上升子序列
#include <bits/stdc++.h>
#define ll long long
using namespace std;
string q;
ll dp[105];
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>q;
for (int i=0;i<105;i++)
{
dp[i] = 1;
}
for (int i=0; i <q.size(); i++)
{
for (int j=0;j<i;j++)
{
if (q[i]>q[j])
{
dp[i]=max(dp[i], dp[j]+1);
}
}
}
sort(dp,dp+105);
cout<<26-dp[104]<<endl;
}
return 0;
}
7-4 Matrix (10分)
Give you an N * N matrix, fill in the number of 1 to N * N in order, for example N = 5, the matrix is as follows
Now let you connect the midpoints of the adjacent two sides, and then only keep the numbers they enclose in the closed graphics area, then the matrix becomes
Now ask you for the sum of all the elements of the changed matrix.
輸入格式:
Input the first line of an integer T (1 <= T <= 100) Next, there is a group test data, and each set of test data is input with an integer N (3 <= N <= 10000) Guaranteed input n is odd
輸出格式:
For each set of test data, output the corresponding answer
輸入樣例:
在這里給出一組輸入，例如：
2
3
5
輸出樣例:
在這里給出相應的輸出，例如：
25
169
題解：
//找規律水題
#include<iostream>
using namespace std;
int main()
{
long long n;
cin>>n;
while(n--)
{
long long m;
cin>>m;
cout<<(1+m*m)/2*(1+m*m)/2<<endl;
}
}
7-5 Jumping Frog（跳蛙） (10分)
A frog is located at the coordinate (x1,y1). He wants to go to the coordinate (x2,y2). He will perform one or more jumps to reach his destination. The rule of the jumping is as follows:
青蛙位于坐標（x1，y1）處，他想轉到坐標（x2，y2），他將進行一次或多次跳躍以到達目的地，跳躍規則如下：
Suppose the frog is located at the coordinate (x,y); then he can jump to the following foursquares:
假設青蛙位于坐標（x，y）處；然后他可以跳到以下四個方格：
(x+y,y)
(x-y,y)
(x,y+x)
(x,y-x)
The Problem: (存在的問題:)
Given the coordinates (x1,y1) and (x2,y2), you need to determine if it is possible for the frog to travel from (x1,y1) to (x2,y2) through a series of jumps as described.
給定坐標（x1，y1）和（x2，y2），您需要確定青蛙是否有可能通過一系列跳躍從（x1，y1）移動到（x2，y2），
The Input:
The first input line contains an integer, n (1 ≤ n ≤ 100), indicating the number of test cases.
第一個輸入行包含一個整數n(1≤n≤100)，表示測驗用例的數量，
Each test case consists of four integers (between -1,000,000,000 to +1,000,000,000 inclusive) separated by a single space denoting x1, y1, x2 and y2, respectively.
每個測驗用例由四個整數(從-1,000,000,000到+1,000,000,000之間)組成，它們之間由一個單獨的空格分隔，分別表示x1、y1、x2和y2，
The Output:
For each test case, output 1 if the frog can travel from (x1,y1) to (x2,y2) through a series of jumps as described or 0 otherwise.
對于每個測驗用例，如果青蛙可以通過描述的一系列跳躍從(x1,y1)移動到(x2,y2)，則輸出1，否則輸出0，
Sample Input:
3
-6 8 17 25
13 17 -16 11
0 0 5 6
Sample Output:
0
1
0
題解：
//由題意知他每次能移動的位移是其坐標的最大公因數的k倍，所以只要最大公因數相同即可
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int gcd(ll a,ll b)
{
if(b==0)return a;
else return gcd(b,a%b);
}//gcd求最大公因數
int main()
{
ll n,x1,x2,y1,y2;
cin>>n;
while(n--)
{
cin>>x1>>y1>>x2>>y2;
if(gcd(abs(x1),abs(y1))==gcd(abs(x2),abs(y2)))cout<<1<<endl;
else cout<<0<<endl;
}
return 0;
}
7-6 求兩圓相交的面積 (10分)
給定2圓的圓心坐標和半徑，計算并輸出兩圓相交的面積，如果是外切或不相交，則輸出0，圓周率取函式值acos(-1)，
輸入格式:
輸入6個整數x1 y1 r1 x2 y2 r2，分別表示兩圓的圓心(x1,y1),(x2,y2)和半徑r1,r2，
輸出格式:
根據圓的位置關系，輸出其相交部分的面積（保留2位小數），
輸入樣例:
在這里給出2組輸入，例如：
0 0 1 2 2 1
2 0 2 5 2 3
輸出樣例:
在這里給出相應的輸出，例如：
0.00
3.22
題解：附一份手寫推導（還在路上）
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
int x1,y1,r1,x2,y2,r2;
cin>>x1>>y1>>r1>>x2>>y2>>r2;
double d=sqrt(pow((x1-x2),2)+pow((y1-y2),2));
if(d>=r1+r2)printf("%.2lf",0);//外切和相離
else if(d<=r1-r2)printf("%.2lf",acos(-1.0)*r2*r2);//兩圓內切，r2小
else if(d<=r2-r1)printf("%.2lf",acos(-1.0)*r1*r1);//兩圓內切，r1小
else//相交
{
double angle1=acos((r1*r1+d*d-r2*r2)/(2*r1*d));//左扇區對應角度
double angle2=acos((r2*r2+d*d-r1*r1)/(2*r2*d));//右扇區對應角度
double s1=angle1*r1*r1;//左扇區對應面積
double s2=angle2*r2*r2;//右扇區對應面積
double s3=r1*d*sin(angle1);//四邊形面積
printf("%.2lf",s1+s2-s3);
}
}
7-7 看電影 (10分)
終于到周末了，明明是特別喜歡看電影，他想在一天內盡量多的看到完整的多部電影， 現在他把他喜歡的電影的播放時間表給你，希望你能幫他合理安排，
輸入格式:
輸入包含多組測驗資料，每組輸入的第一行是一個整數n（n<=100），表示明明喜歡的電影的總數， 接下來n行，每行輸入兩個整數si和ei（1<=i<=n），表示第i個電影的開始和結束時間，為了簡化問題，每個時間都用一個正整數表示， 當n=0時，輸入結束，
輸出格式:
對于每組輸入，輸出能完整看到的電影的個數，
輸入樣例:
在這里給出一組輸入，例如：
12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0
輸出樣例:
在這里給出相應的輸出，例如：
5
題解（曹哥哥）：
#include<iostream>
#include<algorithm>
using namespace std;
struct film
{
int a;
int b;
};
bool cmp(film x, film y)
{
return x.b < y. b;
}
int main()
{
int n;
while(cin>>n)
{
if(n==0)break;
int sum=0,i;
film f[101];
for(i=0;i<n;i++)cin>>f[i].a>>f[i].b;
sort(f,f+n,cmp);//對結束時間進行排序
int m=0;
for(i=0;i<n;i++)
{
if(f[i].a>=m)//從啟示時間遍歷
{
sum++;
m=f[i].b;
}
}
cout<<sum<<endl;
}
return 0;
}
7-8 谷歌的招聘 (10分)
2004 年 7 月，谷歌在硅谷的 101 號公路邊豎立了一塊巨大的廣告牌（如下圖）用于招聘，內容超級簡單，就是一個以 .com 結尾的網址，而前面的網址是一個 10 位素數，這個素數是自然常數 e 中最早出現的 10 位連續數字，能找出這個素數的人，就可以通過訪問谷歌的這個網站進入招聘流程的下一步，
自然常數 e 是一個著名的超越數，前面若干位寫出來是這樣的：e = 2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921… 其中粗體標出的 10 位數就是答案，
本題要求你編程解決一個更通用的問題：從任一給定的長度為 L 的數字中，找出最早出現的 K 位連續數字所組成的素數，
輸入格式：
輸入在第一行給出 2 個正整數，分別是 L（不超過 1000 的正整數，為數字長度）和 K（小于 10 的正整數），接下來一行給出一個長度為 L 的正整數 N，
輸出格式：
在一行中輸出 N 中最早出現的 K 位連續數字所組成的素數，如果這樣的素數不存在，則輸出 404，注意，原始數字中的前導零也計算在位數之內，例如在 200236 中找 4 位素數，0023 算是解；但第一位 2 不能被當成 0002 輸出，因為在原始數字中不存在這個 2 的前導零，
輸入樣例 1：
20 5
23654987725541023819
輸出樣例 1：
49877
輸入樣例 2：
10 3
2468024680
輸出樣例 2：
404
題解：
#include<bits/stdc++.h>
using namespace std;
bool isprime(int n)
{
if (n<=1)//特判1不是質數
{
return false;
}
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
return false;
}
}
return true;
}
int main()
{
int a,b,n;
cin>>a>>b;
string s,s2;
cin>>s;
for(int i=0;i<=a-b;i++)
{
s2=s.substr(i,b);//從下標為i開始截取長度為b位
n=stoi(s2);//string to int 字面意思
if(isprime(n))
{
cout<<s2<<endl;
return 0;
}
}
cout<<"404"<<endl;
return 0;
}
7-9 漢諾塔問題 (10分)
漢諾塔是一個源于印度古老傳說的益智玩具，據說大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤，大梵天命令僧侶把圓盤移到另一根柱子上，并且規定：在小圓盤上不能放大圓盤，每次只能移動一個圓盤，當所有圓盤都移到另一根柱子上時，世界就會毀滅，
題圖1.jpg
請撰寫程式，輸入漢諾塔圓片的數量，輸出移動漢諾塔的步驟，
輸入格式
圓盤數 起始柱 目的柱 過度柱
輸出格式
移動漢諾塔的步驟
每行顯示一步操作，具體格式為：
盤片號: 起始柱 -> 目的柱
其中盤片號從 1 開始由小到大順序編號，
輸入樣例
3
a c b
輸出樣例
1: a -> c
2: a -> b
1: c -> b
3: a -> c
1: b -> a
2: b -> c
1: a -> c
題解：
//運用整體思想，把最下面盤和上面所有盤看作兩部分，回圈遞回
#include<iostream>
using namespace std;
void hano(int n,char x,char y,char z)//起始柱 目的柱 過度柱
{
if(n==1)printf("%d: %c -> %c\n",n,x,y);
else
{
hano(n-1,x,z,y);
printf("%d: %c -> %c\n",n,x,y);
hano(n-1,z,y,x);
}
}
int main(){
int n;
char x,y,z;
cin>>n>>x>>y>>z;
hano(n,x,y,z);
}
7-10 運算式求值 (10分)
機器人卡多掌握了加減法運算以后，最近由學會了一些簡單的函式求值，比如，它知道函式min(20, 23)的值是20, add(10, 98)的值是108等等，經過訓練，機器人卡多甚至會計算一種嵌套的更復雜的運算式，
假設運算式可以簡單定義為： 1、 一個正的十進制數x是一個運算式， 2、 如果x和y是運算式，則函式min(x, y)也是運算式，其值為x，y中的最小數， 3、 如果x和y是運算式，則函式max(x, y)也是運算式，其值為x，y中的最大數， 4、 如果x和y是運算式，則函式add(x,y)也是運算式，其值為x，y之和， 5、 如果x和y是運算式，則函式sub(x,y)也是運算式，其值為x，y之差， 例如，運算式 max(add(1,2),7)的值為7，
請你撰寫程式，對于給定的一組運算式，幫助Dr.Kong算出正確答案，以便校對卡多計算的正誤，
輸入格式:
第一行：N表示要計算的運算式個數(1≤N≤10) 接下來有N行，每行是一個字串，表示待求值的運算式， （運算式中不會有多余的空格，每行不超過300個字符，運算式中出現的十進制數都不超過1000），
輸出格式:
輸出有N行，每一行對應一個運算式的值，
輸入樣例:
在這里給出一組輸入，例如：
3
add(1,2)
sub(1,999)
add(min(1,1000),add(100,99))
輸出樣例:
在這里給出相應的輸出，例如：
3
-998
200
題解（閆神）：
#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
const int N = 103100;
stack <int> op;
// 存盤add, max, min, sub 這些運算子
// add = -1, sub = -2, min = -3 , max = -4
stack <int> number;
// 存盤整數
char a[N];
int main()
{
int T;
cin >> T;
for(int t=1; t<=T; t++) {
memset(a,0,sizeof(a));
cin >> a;
int len =strlen(a); // len 字串a 的長度
for(int i=0; i<len; i++) {
if(a[i] == ')') // 找到 ')' 前面為目前的最小項
{ // 把最小項轉換成數值入堆疊
int optemp = op.top();
op.pop();
int x = number.top();
number.pop();
int y = number.top();
number.pop();
if(optemp == -1) number.push(x+y);
else if(optemp == -2) number.push(y-x);
else if(optemp == -3) number.push(min(x,y));
else if(optemp == -4) number.push(max(x,y));
}
else if(a[i] == 'a' && a[i+1] == 'd') // 找到add, op 入堆疊 -1
op.push( -1 );
else if(a[i] == 's' && a[i+1] == 'u') // 找到sub, op 入堆疊 -2
op.push( -2 );
else if(a[i] == 'm' && a[i+1] == 'i') // 找到min, op 入堆疊 -3
op.push( -3 );
else if(a[i] == 'm' && a[i+1] == 'a')
op.push( -4 );
else if(isdigit(a[i])) { // 找到數字，求他的值，入堆疊到 number
int temp = 0;
while(isdigit(a[i])) {
temp = temp*10 + a[i]-'0';
i++;
}
i--;
number.push(temp);
}
}
cout << number.top() << endl;
number.pop();
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/246173.html
標籤：其他