科大晋校第三次周训(C语言网)
本次出题前五道简单，后五道的确不简单，不过可以尝试一下，我也花了不少时间做后五道。的确太难的我会再题解里面说明，等能力够了的时候再去解决！！！希望大家都能解决每次周训遗留下来的问题，不留遗憾！！！不会的可以在群里提问，共同提高自己！！！
问题 1009: [编程入门]数字的处理与判断
时间限制: 1Sec 内存限制: 128MB 提交: 13225 解决: 6202
题目描述
给出一个不多于5位的整数，要求 1、求出它是几位数 2、分别输出每一位数字 3、按逆序输出各位数字，例如原数为321,应输出123
输入
一个不大于5位的数字
输出
三行 第一行 位数 第二行 用空格分开的每个数字，注意最后一个数字后没有空格 第三行 按逆序输出这个数
样例输入
12345
样例输出
5
1 2 3 4 5
54321
题解：
计算位数：可以取除（/10），直到取到0，看看能取多少次。此处用num++计数。
正序输出：将取余的每一位存到数组，逆序输出，因为存的时候是从后往前存的。
逆序输出：将取余的每一位存到数组，正序输出。
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
#define mod 9999999
#define maxn 10005
void f(int a)//求位数 12345
{
int b[10];
int num=0,i=0;
while(a)
{
b[i++]=a%10;
a/=10;
num++;
}
cout<<num<<endl;
for(int j=i-1;j>=0;j--)
{
cout<<b[j]<<" ";
}
cout<<endl;
for(int j=0;j<i;j++)
{
cout<<b[j];
}
cout<<endl;
}
int main()
{
int n;
cin>>n;
f(n);
return 0;
}
问题 1022: [编程入门]筛选N以内的素数
时间限制: 1Sec 内存限制: 128MB 提交: 5213 解决: 3474
题目描述
用简单素数筛选法求N以内的素数。
输入
N
输出
2～N的素数
样例输入
100
样例输出
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
题解：n以内质数，就是求质数，输出。从2开始，判断到n，是质数的标记为1，不是就标记为0，break；然后输出就好，可以用b来遍历，从2 开始，遍历到a,退出。写法while（b<=a）就行。。
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
#define mod 9999999
#define maxn 10005
void f(int a)
{
int k;
int b=2;
while(b<=a)
{
k=1;
for(int i=2;i*i<=b;i++)
{
if(b%i==0)
{
k=0;
break;
}
}
if(k)
cout<<b<<endl;
b++;
}
}
int main()
{
int n;
cin>>n;
f(n);
return 0;
}
问题 1120: 【C语言训练】"水仙花数"问题2
时间限制: 1Sec 内存限制: 128MB 提交: 1652 解决: 1156
题目描述
输出所有的"水仙花数".所谓"水仙花数"是指这样的一个三位数：其各位数字的立方和等于该数本身。例如：371是一个"水仙花数"，371=33+73+1^3.
输入
无
输出
输出所有的"水仙花数"(从小到大的顺序输出,一行一个)
样例输入
无
样例输出
无
题解：题目说了，是三位数，所以可以for循环100到999之间，符合情况的则输出。
还是对其取余，再取除，直到为零。将余数三次方后累加到sum,最后判断一下是否和原数相同，相同则输出此数。
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
#define mod 9999999
#define maxn 10005
void f(int a)
{
int sum=0,b,c=a;
while(c)
{
b=c%10;
c/=10;
sum+=(b*b*b);
}
if(sum==a)
cout<<a<<endl;
}
int main()
{
for(int i=100;i<1000;i++)
{
f(i);
}
return 0;
}
问题 1133: 【C语言训练】求1+2!+3!+…+N!的和
时间限制: 1Sec 内存限制: 128MB 提交: 2794 解决: 782
题目描述
求1+2!+3!+…+N!的和
输入
正整数N（N〈=20）
输出
1+2!+3!+…+N!的和 (结果为整数形式)
样例输入
3
样例输出
9
题解：
可以直接for循环1到n的每一位阶乘再进行累加，输出。阶乘数字较大，超出了int的范围，最好用long long，可以存储18位数，int可以存储9位，差不多这样，。算阶乘可以for循环乘过去，也可以用递归，n的阶乘等于n*(n-1)的阶乘，重复子问题，如果a==1;return 1; else return a*f(a-1);
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
#define mod 9999999
#define maxn 10005
ll f(ll a)
{
if(a==1)
return 1;
return a*f(a-1);
}
int main()
{
ll n,sum=0;
cin>>n;
for(int i=1;i<=n;i++)
{
sum+=f(i);
}
cout<<sum<<endl;
return 0;
}
问题 1144: 【C语言训练】自守数问题
时间限制: 1Sec 内存限制: 128MB 提交: 803 解决: 488
题目描述
自守数是指一个数的平方的尾数等于该数自身的自然数。
例如：
25^2=625
76^2=5776
9376^2=87909376
请求出200000以内的自守数?
输入
无
输出
200000以内的自守数(包括0, 数之间用两个空格分开，末尾无空格)
样例输入
无
样例输出
0 1 5 6 25 76 376 625 9376 90625 109376
题解：题目意思是一个数的平方后末尾仍然包含这个数就称为自守数。
可以这么想，平方数%此数对应的10得倍数，如果和此数相等则符合条件。
eg: 25 平方为：625 ，25是两位数,所以对应100，让625%100取余，结果是25则符合条件，很明显，是的，所以这样可以用来判断自守数。
还是老套路，对其取余，再取除，直到为零，同时计算其对应的10的倍数，及代码中定于的b,从1开始，while循环一次，就给他自己乘10.
最后判断一下a*a%b==a是否成立，成立了就输出即可。
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
#define mod 9999999
#define maxn 10005
ll f(ll a)
{
ll num=0,b=1,c=a;
while(c)
{
c/=10;
num++;
b*=10;
}
if(a*a%b==a)
return 1;
else
return 0;
}
int main()
{
ll n;
//或者直接输出，我介意用程序算一下，别钻题目漏洞
//cout<<"0 1 5 6 25 76 376 625 9376 90625 109376"<<endl;
for(int i=0;i<=200000;i++)
{
if(f(i)&&i)
cout<<" "<<i;
if(f(i)&&i==0)
cout<<i;
}
return 0;
}
问题 1076: 内部收益率
时间限制: 1Sec 内存限制: 128MB 提交: 377 解决: 152
题目描述
在金融中，我们有时会用内部收益率IRR来评价项目的投资财务效益，它等于使得投资净现值NPV等于0的贴现率。换句话说，给定项目的期数T、初始现金流CF0和项目各期的现金流CF1, CF2, …，CFT，IRR是下面方程的解：
为了简单起见，本题假定：除了项目启动时有一笔投入（即初始现金流CF0 < 0）之外，其余各期均能赚钱（即对于所有i=1,2,…,T，CFi > 0）。根据定义，IRR可以是负数，但不能大于-1。
输入
输入文件最多包含25组测试数据，每个数据占两行，第一行包含一个正整数T（1<=T<=10），表示项目的期数。第二行包含T+1个整数：CF0, CF1, CF2, …, CFT，其中CF0 < 0, 0 < CFi < 10000 (i=1,2,…,T)。T=0表示输入结束，你的程序不应当处理这一行。
输出
对于每组数据，输出仅一行，即项目的IRR，四舍五入保留小数点后两位。如果IRR不存在，输出"No"，如果有多个不同IRR满足条件，输出"Too many"（均不含引号）
样例输入
1
-1 2
2
-8 6 9
0
样例输出
1.00
0.50
题解：此题较难想到做法，因为相当于解一个方程，未知数还是不一样的次方，无法直接去做。
所以用到二分法，确定一个区间，每次循环判断解的范围，逐渐缩小区间，直到得到的解近似接近于最终答案，退出循环，输出答案。
二分具体操作：就是对区间取中点；根据结果判断范围，缩小范围
解题思路:irr的取值范围是（-1，+无穷大）
p其实就是计算当前解可以得到的最终答案，最后用于判断
当 irr -> -1 时候，表达式为正值，相当于高数的极限
当 irr —> 无穷大时候， 表达式为负值
因此必有一个解在该区间上。[-1,无穷大]（因为表达式为0，所以一定在此区间）
使用二分法进行暴力计算
找到近似的irr
注意事项：
pow(a,b）函数表示a的b次，是cmath头文件下专门计算次方的函数
还有fabs(a)函数，也是cmath头文件下用来计算绝对值的函数。
因为用到了小数，最好使用double, 控制最好写为 %lf 。
还有1e a，表示10的a次方。
要想答案接近0，可以判断此次p累加的结果的绝对值是否小于10的-6次，即0.000001的精度，这样可以得到一个最终答案。将其用printf来控制小数位。
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
#define mod 9999999
#define maxn 10005
//二分，逐渐缩小区间，直到找到最近似的值
/* 解题思路:irr的取值范围是（-1，+无穷大） p其实就是计算当前解可以得到的最终答案，最后用于判断 当 irr -> -1 时候，表达式为正值，相当于高数的极限 当 irr —> 无穷大时候， 表达式为负值 因此必有一个解在该区间上。[-1,无穷大]（表达式为0，所以一定在此区间） 使用二分法进行暴力计算 找到近似的irr */
int main()
{
int T;
int cf[100];
while(cin>>T&&T!=0)
{
for(int i=0;i<=T;i++)
cin>>cf[i];
double x=-1.0,y=1e6,irr,p;
for(int j=0;j<100;j++)
{
irr=(x+y)/2;//二分取当前区间的中间值
p=0;
for(int k=0;k<=T;k++)//将T个数都计算出来
{
p+=cf[k]/(pow(1+irr,k));// pow(a,b),求a的b次
}
if(fabs(p)<10e-6)//cmath fabs()求绝对值//p应该无限接近0，所以要小于1e-6
break;
if(p<0)//说明irr值太大，缩小右端点
y=irr;
if(p>0)//说明irr值太小，缩小左端点
x=irr;
}
printf("%.2lf\n",irr);
}
return 0;
}
问题 1094: 字符串的输入输出处理
时间限制: 1Sec 内存限制: 64MB 提交: 7072 解决: 2326
题目描述
字符串的输入输出处理。
输入
第一行是一个正整数N，最大为100。之后是多行字符串（行数大于N）， 每一行字符串可能含有空格，字符数不超过1000。
输出
先将输入中的前N行字符串（可能含有空格）原样输出，再将余下的字符串（不含有空格）以空格或回车分割依次按行输出。每行输出之间输出一个空行。
样例输入
2
www.dotcpp.com DOTCPP
A C M
D O T CPP
样例输出
www.dotcpp.com DOTCPP
A C M
D
O
T
CPP
题解：此题也不简单，他没说输多少结束，说明他又是一个死循环，所以最好输入一组咱们就对其处理输出一组。
前n项原样输出，先处理前n项，用getline(cin,str);来读入空格，因为cin输不进去空格。然后直接cout输出就行。看好格式，要输出两个换行。。
后面的我判断的空格和换行输出，但是这样总提示错误百分之33，我没想到解决办法，但是有更好的处理办法，。
最好的处理办法：直接while(cin>>str)，然后直接输出，我不是说过cin读入不了空格吗？没错，cin输入的数据都放到了缓存器中，到该输出的时候他会从其中取出来，但是遇到空格他就自动截断，输出空格前面的，但是如果你只输出一次就出现了输不出空格的情况了，但是你要输出好几次，直到结束的话，他会将缓存器中放的字符都赋值给str,再次输出时，就输出从当前空格到下一个空格之间的数据，直到遇到换行结束，开始下一次的输入操作。
赋值时同时自动过滤空格，将除了空格以外的字符赋值过去。
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
#define mod 9999999
#define maxn 10005
int main()
{
string str;
int n,i=0;
cin>>n;
getchar();//接收回车字符
for(i=0;i<n;i++)
{
getline(cin,str);
cout<<str<<endl<<endl;
}
//自认为这样写没问题，但是老提示错误33%
// while(getline(cin,str))
// {
// for(int j=0;j<str.length();j++)
// {
// if(str[j]==' ')
// {
// cout<<endl<<endl;
// }
// else
// {
// cout<<str[j];
// }
// }
// }
while(cin>>str)
{
cout<<str<<endl<<endl;
}
return 0;
}
问题 1097: 蛇行矩阵
时间限制: 1Sec 内存限制: 64MB 提交: 3784 解决: 2424
题目描述
蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。
输入
本题有多组数据，每组数据由一个正整数N组成。（N不大于100）
输出
对于每一组数据，输出一个N行的蛇形矩阵。两组输出之间不要额外的空行。矩阵三角中同一行的数字用一个空格分开。行尾不要多余的空格。
样例输入
5
样例输出
1 3 6 10 15
2 5 9 14
4 8 13
7 12
11
题解：这道题也不太简单。先计算每行第一个数，其实就是2的行数次方，用一个函数ff()来计算一下。
定义变量num和temp，分别用来计算每一行之间的差值，和每一列之间的差值.
一行过后，列差值要加一,即temp++
一个数据以后行差值也要加一，即num++
每一行的第二个数开始之间的差值都要从当前列差值开始加1，输出一个数加一次1.即num=temp,然后开始回归正常进行++
变量pos在外层要计算每一层第一个数。内层要进行加一直在变的num,来得到下一个数后再进行输出。
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
#define mod 9999999
#define maxn 10005
int ff(int a)//计算每行第一个数
{
int k=1,b=1;
for(int i=1;i<a;i++)
{
b+=k++;
}
return b;
}
int main()
{
int n,k,num=2,temp=2,pos;
cin>>n;
k=n;
for(int i=1;i<=n;i++)
{
num=temp;
pos=ff(i);
cout<<pos;//先输出每行第一个数
for(int j=0;j<k-1;j++)
{
pos+=num;
cout<<" "<<pos;
num++;
}
k--;//每行比上一行少一个数字
temp++;//每行两数之间的差比上一行多一
cout<<endl;
}
return 0;
}
问题 1117: K-进制数
时间限制: 1Sec 内存限制: 128MB 提交: 1057 解决: 400
题目描述
考虑包含N位数字的K-进制数. 定义一个数有效, 如果其K-进制表示不包含两连续的0.
考虑包含N位数字的K-进制数. 定义一个数有效, 如果其K-进制表示不包含两连续的0.
例:
1010230 是有效的7位数
1000198 无效
0001235 不是7位数, 而是4位数.
给定两个数N和K, 要求计算包含N位数字的有效K-进制数的总数.
假设2 <= K <= 10; 2 <= N; 4 <= N+K <= 18.
输入
两个十进制整数N和K
输出
十进制表示的结果
样例输入
2
10
样例输出
90
此题并不简单，你能想到的办法，可以实现功能，但会超时，因为用到了数据结构与算法的DFS,对于我们来说可能就变难了。但最好都涉及一下。
题解一：调用函数超时，改进：将函数写到主函数里，直接计算，仍然超时。。。此方法不会通过，但思路没有问题，需要更高效的算法，见题解二。
解释：救赎k进制，判断是否有相邻的0。
可能你们又对k进制不熟悉了，没关系，类比一下10进制，一样样的，10进制做法：先%10 ，再 /10，直到为零，所以k进制就是将10换为k,像这样：先 %k，再 /k，直到为零。
将取余得到的结果存到数组，判断一下当前位置数组值和上一个位置数组值是否同时为零。是的话说明它不是有效数。循环完没有相邻的0则说明它是有效数，退出while,使num++.
关于n位数，也就是从当前10的n次方到10的n+1次方之间进行循环。
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
#define mod 9999999
#define maxn 10005
int num;
//调用函数超时太大
void f(int a,int k)
{
int arr[100],i=0;
while(a)
{
arr[i++]=a%k;
a/=k;
if(arr[i-1]==0&&arr[i-2]==0)
return;
}
num++;
}
int main()
{
ll a=1,b;
int n,k;
cin>>n>>k;//2 10
for(int i=1;i<n;i++)//计算n位数的起始数
{
a*=10;
}
for(int j=a;j<a*10;j++)
{
int arr[100],i=0,m=1,temp=j;//m用来标记是不是符合条件，初始化为1
while(temp)
{
arr[i++]=temp%k;
temp/=k;
if(arr[i-1]==0&&arr[i-2]==0&&i!=1)//细节：判断是不是第一位数，因为第一位数没有上一位，最好不要进入判断。
{
m=0;break;
}
}
if(m)
num++;//符合条件，就num++
}
cout<<num<<endl;
return 0;
}
题解二：DFS深搜，目前可以先不用了解，基础好点的可以看一下，拓宽一下思路，欢迎大家也来研究一下！！！
dfs就是递归，递归流程又不太好理解。。
具体题解：用到了DFS，它的作用是一条路走到黑，走到死路则回到上一条路，继续往下走，难理解的地方在于递归的调用自己，他的执行流程不好理解，。这道题要想转化为k进制，可以模拟一下每一位数的取值，每一位都可以取0到k-1，eg:十进制可以取0到9，就这个意思。
先模拟第一位，for循环就是用来模拟一位上可以的取值，if条件是用来判断当前取的数，判断第一位是不是0，以及有没有相邻的两个0，有的话说明不符合条件，继续下一次for循环，直到找到一个合理的数，再进行下一次dfs(cur+1)，找下一位，。每次的dfs(）是在前一位已经找到和找完0到k-1没有找到的情况下才进行的，下一位找到后回到上一次调用dfs之前，进行第二位的第二种情况探索，直到将第二位所有数情况走完，才会回到第一位的下一种情况探索，直到第一位情况探索完，结束这次dfs()递归，。
具体流程：以n=2,k=10为例，先调用dfs(0),再调用dfs(1),再调用dfs(2),cur == n，所以回到上一次dfs(1),则回到此处dfs所在的for循环进行查找下一种符合条件的情况，找到后继续dfs(2),cur == n，回到dfs(1),继续下一种情况，直到情况查找结束，回到dfs(0),继续for循环，找到情况，继续dfs(1),继续dfs(2),然后cur == n,继续回退到dfs(1),找完后继续回退到dfs(0),for循环也结束后退出函数，程序结束。
宏观概括：dfs(0) 到dfs(1) 到dfs(2) 到dfs(1) 到dfs(0)退出 ，他会遍历完所有情况，符合条件的都会走到cur==n时，进行cnt++;
他能走到cur==n，说明已经找到一种符合条件的组合数，让计数器cnt++;
退出每一次dfs()的条件是cur==n，或者for循环结束。
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
#define mod 9999999
#define maxn 10005
char s[10];
int cnt=0,n,k;
void dfs(int cur)
{
if( cur == n)// 走到这里说明已经找完了n位数字，是一种有效情况，让cnt++;计数。
{
cnt++;
return;//回到上一次dfs
}
else
{
for(int i=0;i<k;i++)// k=10
{
s[cur]=i+'0';//将i转化为整型 方法：+'0';
if(s[0]=='0'||(s[cur]=='0'&&s[cur-1]=='0'))//不符合条件则继续下一次for循环
continue;
else
dfs(cur+1);//每次调用结束都会回到这里，进行下一次for循环
}
}
}
int main()
{
cin >> n >> k;//2 10
dfs(0);
cout << cnt ;
return 0;
}
问题 1105: 数列
时间限制: 1Sec 内存限制: 128MB 提交: 793 解决: 241
题目描述
给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k=3时，这个序列是：
1，3，4，9，10，12，13，…
（该序列实际上就是：30，31，30+31，32，30+32，31+32，30+31+32，…）
请你求出这个序列的第N项的值（用10进制数表示）。
例如，对于k=3，N=100，正确答案应该是981。
输入
输入只有1行，为2个正整数，用一个空格隔开：
k N
（k、N的含义与上述的问题描述一致，且3≤k≤15，10≤N≤1000）。
输出
输出计算结果是一个正整数（在所有的测试数据中，结果均不超过2.1*109）。（整数前不要有空格和其他符号）。
样例输入
3 100
样例输出
981
题解：此题可以看一下每一项和前面所有项的联系。
eg:
3^0(第1项)
3^1(第2项) 3^0+3^1(第3项)
3^2(第4项) 3^0+3^2(第5项) 3^1+3^2(第6项) 3^0+3^1+3^2(第7项) //4 5 6 7
可以先计算每一行第一项，即3的行数次方。
每一行的第一项的项数都是2的行数次方如果是每行的第一项则直接计算2的行数次方，并存入数组。并用中间变量保存此时第一项的值。方便此行后面数据的运算。
每一行第一项之后的数据：
arr[i]=temp+arr[i-f(2,m-1)]; 可以用当前行第一项依次去加前面每一项和。temp为此行第一项的值， i-f(2,m-1)这样表示可以找出从第一项到此行第一项之前所有数的下标，因为i是动态改变的。f(2,m-1)，m-1，因为当前行计算第一项的时候，m进行了++，所以要减回去。。。
n的范围是1000，你可以算到1005，然后输出题目要求的第n项，输出arr[n]就好。
当然求次方可以用到pow(a,b)函数，可以简化代码。欢迎大家使用！！！
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
#define mod 9999999
#define maxn 10005
/* 3^0(第1项) 3^1(第2项) 3^0+3^1(第3项) 3^2(第4项) 3^0+3^2(第5项) 3^1+3^2(第6项) 3^0+3^1+3^2(第7项) //4 5 6 7 */
//3≤k≤15 10≤N≤1000
int f(int n,int a)//n的a次
{
int k=1;
for(int i=0;i<a;i++)
{
k*=n;
}
return k;
}
int main()
{
int k,n,m=0;
int temp;
cin>>k>>n;//3 4
int arr[1010];
for(int i=1;i<=1005;i++)
{
if(i==f(2,m))//2的m次//每行第一个数
{
arr[i]=f(k,m);
temp=arr[i];
m++;
}
else
{
arr[i]=temp+arr[i-f(2,m-1)];//arr[i-f(2,m-1)] i-f(2,m-1)可以计算到第一项到此行之前每一项的下标
}
}
cout<<arr[n]<<endl;
return 0;
}
投递美团等公司9个岗位