C/CPP基础PTA习题及分析
数组
数组排位
已知素数序列为2、3、5、7、11、13、17、19、23、29……，即素数的第一个是2，第二个是3，第三个是5……那么，随便挑一个数，若是素数，能确定是第几个素数吗？如果不是素数，则输出0。
输入格式:
测试数据有多组，处理到文件尾。每组测试输入一正整数N（1≤N≤1000000）。
输出格式:
对于每组测试，输出占一行，如果输入的正整数是素数，则输出其排位，否则输出0。
输入样例:
2
6
4
5
13
991703输出样例:
1
0
0
3
6
77901C/CPP
#include <iostream>
#include <cmath>
using namespace std;
const int N = 1000000 + 10;
int a[N];
bool prime(int x)//判断素数
{
if (x == 1)return false;
for (int i = 2; i <= sqrt(x); i++)
{
if (x % i == 0)return false;
}
return true;
}
void panDuan(int n)
{
int i = 0;
for (int i = 1; i <= n; i++)
{
if (prime(n))i++;
}
cout << i << endl;
}
int main()
{
int a;
while (scanf_s("%d",&a) != EOF)
{
panDuan(a);
}
system("pause");
return 0;
}#include <iostream>
#include <cmath>
using namespace std;
const int N = 1000000+10;
int a[N];
void init(int n)//初始化
{
for(int i = 1;i <= n;i ++ )a[i]=i;
}
bool prime(int x)//判断素数
{
if(x==1)return false;
for(int i = 2;i <= sqrt(x);i ++ )
{
if(x%i==0)return false;
}
return true;
}
int main()
{
int n;
while(cin>>n)
{
if(!prime(n))
{
cout<<"0"<<endl;
continue;
}
init(n);
a[1]=0;//排除1
for(int i = 2;i <= sqrt(n);i ++ )
{
for(int j = 1;j <= n;j ++ )
{
if(j%i==0)a[j]=0;
if(prime(i))a[i]=i;//若i为素数则不做处理，防止漏数据
}
}
int idx=0;//素数位数计数
for(int i = 2;i <= n;i ++ )
{
if(a[i]>0)
{
idx++;
if(a[i]==n)break;
}
}
cout<<idx<<endl;
}
}#include <iostream>
using namespace std;
const int N = 1000000;
int main()
{
int index[N] = {1}; int cnt = 1;
for (int i = 0; i < N; i++)
{
index[i] = 1;
}
index[0] = 0;index[1] = 0;
for (int i = 2; i <=N; i++)
{
if (index[i] == 0)continue;
index[i] = cnt;
cnt += 1;
for (int j = i * i; j <=N; j += i)
{
index[j] = 0;
}
}
int a;
while (scanf("%d", &a) != EOF) {
cout << index[a] << endl;
}
return 0;
}素数优化：
#include <iostream>
#include <math.h>
using namespace std;
//素数优化！详见素数优化文章
bool prime(int m) {
int i = 0;
if (m>= 0 && m <= 8)
{
if(m==2 || m==3 || m==5 || m==7)return 1;
else return 0;
}
for (i = 3; i <= sqrt(m); i += 2)
if (m % i == 0) return 0;
if (i >= sqrt(m)) return 1;
else return 0;
}
int get_prime(int N){
int n =1;
for (int i =3 ; i <= N; i+=2){
if (prime(i)){
n++;
}
}
return n;
}
int main(){
int a;
while (scanf("%d",&a) != EOF){
prime(a)?cout<<get_prime(a)<<endl:cout<<0<<endl;
}
return 0;
}Python
N = 1000000
index = [1]*(N+1)
def f():
index[0] = index[1] = 0
cnt = 1
for i in range(2,N + 1):
if index[i] == 0:
continue
index[i] = cnt
cnt += 1
for j in range(i * i,N+ 1,i):
index[j]=0
f()
try:
while True:
n = int(input())
print(index[n])
except EOFError:pass计算字符串数组长度
从键盘任意输入一个字符串，用数组的方式计算其实际字符个数并打印出来，即不使用字符串处理函数strlen（）编程实现strlen的功能。
函数接口:
unsigned int MyStrlen(const char str[])输入格式:
字符串
输出格式:
字符串长度
输入样例:
在这里给出一组输入。例如：
hello world输出样例:
在这里给出相应的输出。例如：
11C\CPP
解法一：
#include<stdio.h>
#include<iostream>
using namespace std;
unsigned int MyStrlen()
{
int i = 0;
while ((getchar() != '\n'))
{
i++;
}
return i;
}
int main()
{
cout << MyStrlen() << endl;
system("pause");
return 0;
}输入：hello world
输出：11
解法二：
问题分析：
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
unsigned int MyStrlen(const char str[])
{
return sizeof(str)/sizeof(char);//注意此时的str是一个指针！
}
int main()
{
char arr[500]={0};
fgets(arr,500,stdin);
cout<<strlen(arr)<<endl;
return 0;
}输入：hello world
输出：8
问题分析：因为使用了函数进行运算，数组退化为指针，所以在MyStrlen()中sizeof计算的实际上是指针的长度，结果出错！
注意易混点：sizeof(arr) / sizeof(char)计算的是数组的长度，而不是数组中字符串的长度！！
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int main()
{
char arr[500] = { 0 };
fgets(arr, 500, stdin);
cout << sizeof(arr) / sizeof(char) << endl;
system("pause");
return 0;
}输入：hello world
输出：500
解法三：
#include<stdio.h>
int main(void)
{
char s[100];
int count = 0;
gets(s);
for (int i = 0; s[i] != '\0'; i++)//注意这种思路更加简洁，等同于for (int i = 0; i<strlen(s); i++)
count++;
printf("%d\n", count);
}
字符串中的数字之和
程序要求能够提取输入的字符串中的数字，将数字累加，得到数字之和，如输入的字符串为”abc76wet23er1.”,应该提取数字76,23,1,求和后，即76+23+1=100，要求输入的字符串最后一个字符不能为数字字符。
输入格式:
输入一个字符串，字符串长度不超过100.
输出格式:
输出字符串中的数字之和
输入样例1:
在这里给出一组输入。例如：
abc76wet23er1.输出样例1:
在这里给出相应的输出。例如：
100输入样例2:
在这里给出一组输入。例如：
wwq100rty23fg45k输出样例2:
在这里给出相应的输出。例如：
168C/CPP
解法一：
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
char arr[100]; int sum = 0;
fgets(arr,100,stdin);
for (int i = 0; i < strlen(arr); i++)
{
if (arr[i] >= '0' && arr[i] <= '9')
sum += arr[i] - '0';
}
cout << sum;
system("pause");
return 0;
}输入：abc76wet23er1.
输出：19
问题：只能计算十以内的数字的和：7+6+2+3+1
解法二：
#include<iostream>
using namespace std;
int main() {
char ch, a;
int sum, count;
sum = 0;
count = 0;
while (~scanf("%c", &ch)) //注意这种写法,便捷。等同于while (scanf("%c", &ch) != EOF)
{
if (ch >= '0' && ch <= '9')
{
count = count * 10 + (ch - '0');
}
else
{
sum += count;
count = 0;
if (ch == '\n' && !(a >= '0' && a <= '9'))
break;
}
a = ch;//记录上一次输入得字符
}
cout << sum << endl;
}删除指定字符
从键盘输入一个字符串给str和一个字符给c，删除str中的所有字符c并输出删除后的字符串str。
输入格式:
第一行是一个字符串，不超过100个字符； 第二行是一个字符。
输出格式:
删除指定字符后的字符串。
输入样例:
在这里给出一组输入。例如：
sdf$$$sdf$$
$输出样例:
在这里给出相应的输出。例如：
sdfsdfC/CPP
解法一：
#include<stdio.h>
#include<string.h> //这里是因为使用了strlen()函数。
int main()
{ int k;
char str[100],c; //因为不知道字符串的具体数值，就假设了他有100个字符。
gets(str);
c=getchar();
k=strlen(str);
int i,j=0; // 删除相同字符
for(i=0;i<k;i++){
if(str[i]!=c){
str[j]=str[i];
j++;
}
}
str[j]='\0'; //字符串的结尾
puts(str);
}解法二：
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
char arr[100],c; int sum = 0;
fgets(arr,100,stdin);cin>>c;
for (int i = 0; i < strlen(arr)-1; i++)
{
if (arr[i] == c)
continue;
else
cout<<arr[i];
}
return 0;
}问题：
#include<stdio.h>
#include<string.h>
int main()
{
char a[100],b;
scanf("%s",a);
scanf("%c",&b);
for(int i=0;i<strlen(a);i++)
{
if (a[i]==b)
continue;
else
printf("%c",a[i]);
}
return 0;
}
问题：
解决：
#include<stdio.h>
#include<string.h>
int main()
{
char a[100],b;
gets(a);
scanf("%c",&b);
for(int i=0;i<strlen(a);i++)
{
if (a[i]==b)
continue;
else
printf("%c",a[i]);
}
return 0;
}
#include<stdio.h>
#include<string.h>
int main()
{
char a[100],b;
scanf("%s",a);
getchar();//清除缓存区的'\n'
scanf("%c",&b);
for(int i=0;i<strlen(a);i++)
{
if (a[i]==b)
continue;
else
printf("%c",a[i]);
}
return 0;
}
判断输入的日期是否正确
功能：
判断传入日期是否合法传入格式：前四位是年，中间两位是月后两位是日，首先判断输入值是否在10000001-99999999之间，之后对传入数值调用int StuIfdat(int year,int month,int day)进行判断是否符合日期规范，year传入年份，month传入月份，day传入日合法该函数会返回0，不合法返回1
C/CPP
#include<stdio.h>
#include<stdlib.h>
int stuIfDat(int year, int month, int day){
int Days[12] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
if (year < 0 || month < 1 || month > 12 || day < 1 || day > Days[month - 1]){
return 1;
}
if (month == 2){
if ((year % 400 == 0) || (year % 100 != 0 && year % 4 == 0)){
Days[1] = 29;
}
}
return 0;
}
int main() {
int n; scanf("%d", &n);
n > 10000001 && n < 99999999 ? stuIfDat(n / 10000, n % 1000 / 100, n % 1000000) : printf("Invalid");
return 0;
}
PS：判断闰年和平年的方法
计算方法：
①、普通年能被4整除且不能被100整除的为闰年。（如2004年就是闰年,1901年不是闰年）
②、世纪年能被400整除的是闰年。(如2000年是闰年，1900年不是闰年)
遇到整百年时（如2000，1900，300）要被400整除才是闰年，否则为平年（2000闰年，1900平年，300平年）；
遇到非整百年时（如2004，2005），只要被4整除就是闰年，不能被4整除为平年（2004闰年，2005平年）。
主对角线、副对角线之和
计算一个N×N（2<=N<=10）整型矩阵的主对角线元素及副对角线元素之和。注意：若某数组元素既在主对角线上又在副对角线上，则只加一次。
输入格式:
输入第一行给出一个正整数N，要求2<=N<=10。随后N行，每行输入N个整数，其间以空格分隔。
输出格式:
输出矩阵主、副对角线元素之和。
输入样例:
在这里给出一组输入。例如：
3
1 3 5
6 7 9
2 4 8输出样例:
在这里给出相应的输出。例如：
23C/CPP
#include<stdio.h>
int main()
{
int a[10][10],n,b,c,d,e,m;
scanf("%d",&n);
for(b=0;b<n;b++)
{
for(c=0;c<n;c++)
{
scanf("%d",&a[b][c]);
}
}
for(b=0;b<n;b++)
{
for(c=0;c<n;c++)
{
if(b==c)
{
d=d+a[b][c];
}
else if(b+c==n-1)
{
d=d+a[b][c];
}
}
}
printf("%d",d);
return 0;
}
易错点：
注意奇数行和偶数行对角线之和不同，偶数行的对角线数之和是可以直接相加的，但是奇数行的对角线直接相加会导致中间元素的重复相加，需要注意。
打印数字金字塔
输入n(0<n<10)后，输出1个数字金字塔。例如输入为4，则输出：
1
222
33333
4444444输入格式:
一个整数n。
输出格式:
一个数字金字塔，第i行输出的数字全为i，总的输出n行。
输入样例:
4输出样例:
1
222
33333
4444444C/CPP
#include<iostream>
using namespace std;
int main()
{
int n;cin >> n;
for (int i = 0; i < n-1; i++)
{
for (int j = 0; j < (n - 1 - i); j++)
{
cout << " ";
}
for (int j = 0; j < 2 * i + 1; j++)
{
cout << i+1;
}
cout << endl;
}
//不打印最后一行的换行产生的空格做的处理
int i = n-1;
for (int j = 0; j < (n - 1 - i); j++)
{
cout << " ";
}
for (int j = 0; j < 2 * i + 1; j++)
{
cout << i+1;
}
return 0;
}
#include<stdio.h>
int main()
{
int i, j, n, t;
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
for (j = 0; j < n - i; j++)
printf(" ");
for (t = 0; t < (2 * i - 1); t++)
{
printf("%d", i);
}
//不打印最后一行的换行产生的空格做的处理
if (i <= n - 1)
printf("\n");
}
}PS：
上面的两个代码的算法相同只是处理最后一个换行的方法不同。下面的处理比较巧妙