[数据结构与算法]21计一第三次题解

第一题

我的想法就是遍历1到n，判断每个数属于哪一类，然后加到那一类上。
题目保证每类数至少有一个，所以肯定不会出现除0导致re的问题

其他的东西看代码就差不多了

#include<cstdio>
//这个头文件差不多等于stdio.h，之后就不赘述了



int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	double sum1=0,sum2=0,num1=0,num2=0;
	for(int i=1;i<=n;i++){
		if(i%k==0)sum1+=i,num1++;
		else sum2+=i,num2++;
		//++ 差不多等价于num1=num1+1
	}
	printf("%.1lf %.1lf\n",sum1/num1,sum2/num2);
	return 0;
}

第二题

首先int的范围最大是2^31-1
所以题目给的n是int范围内的

n是由两个不同质数的乘积构成，要求大的质数

n本身是合数，质数是从2开始的
所以枚举的范围是2-n-1(闭区间)

因为n只有质数因子（除了1和n）
所以枚举的i如果是n的因子必然是质数
n/i就是较大的质数因子了

枚举到了因子就直接break跳出循环，节约一点时间开销

质数的开篇题

#include<cstdio>
#include<cstring>
//cstring 也差不多等于string.h，个人习惯理解一下，虽然这道题没用到
int main(){
	int n;
	scanf("%d",&n);
	for(int i=2;i<n;i++){
		if(n%i==0){printf("%d\n",n/i);break;}
	}
	return 0;
}

第三题

先上代码

#include<cstdio>
#include<cstring>
int if_prime(int x){
	if(x==1)return 0;
	if(x==2)return 1;
	if(x==3)return 1;
	for(int i=2;i*i<=x;i++){
		if(x%i==0)return 0;
	}
	return 1;
}
int main(){
	int n;
	scanf("%d",&n);
	int ans=0,sum=0;
	for(int i=2;i<=n;i++){
		if(if_prime(i)&&sum+i<=n){
			sum+=i;
			ans++;
			printf("%d\n",i);
		}
	}
	printf("%d\n",ans);
	return 0;
}

最开始的if_prime函数是用来判断x的质数性的，可以写的更美观一点（同学们自行改改吧，如果有强迫症的话）

显然ans是质数个数，而sum是目前的质数和
其他的东西在代码里应该比较好理解

第四题

回文质数
有点烦
我没看题目下面的提示，我的思路就是打个质数表，然后看是不是回文的

#include<cstdio>
#define MAXN 10000005
 //偶数位数回文数（除11）必定不是质数,所以只要运行到10000000.这个是一个结论。记一下吧
int prime[MAXN];//质数表
bool pp[MAXN];
//这个变量就是有两种情况 false 也就是0 表示错   true 1 表示对  赋值 1和赋值 0 一个效果
void get_prime(){
    //筛法求质数表.谢大之后应该会教
    for(int i=1;i<MAXN;i++){
        pp[i]=true;
    }
    pp[1]=false;

    for(int i=2;i*i<=MAXN;i++){
        if(pp[i]){
            for(int j=i*i;j<MAXN;j+=i)pp[j]=false;
        }
    }
}

bool if_h(int x)//这个是判断回文数，主要的思路就是利用整数反转，看看反转后和原来是不是一样的
{

    int y=x,num=0;//int y=x,防止x被改变
    while (y!=0)
    {
        num=num*10+y%10;//上一次数字的记录进位再加上下一位数
        y/=10;
    } 
    if (num==x) return 1;
    else return 0;
}
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    
    get_prime();

    for(int i=a;i<=b;i++)
    {
        if(i>10000000) //肯定不是回文质数
            break;
        if(if_h(i)&&pp[i]) printf("%d\n",i);//如果同时满足回文加质数就输出
    }
    return 0;
}

第五题

一个普普通通的打图像题
要领也就一个，找规律

#include<cstdio>
#include<cstring>
int main(){
	int n;scanf("%d",&n);
	//上方的矩阵是每行n个，一共n列
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int k=j+(i-1)*n;//推算出i行j 要打什么数
			printf("%02d",k);
		}
		printf("\n");
	}
	printf("\n");//中间一个空行

	int cnt=1;
	for(int i=1;i<=n;i++){//n行
		for(int j=2*(n-i);j>=1;j--){//第一行要打1个 数 第i行要i个数
		//那么就要2*n-2*i个空格
			printf(" ");
		}
		for(int j=1;j<=i;j++){
			printf("%02d",cnt++);
		}
		printf("\n");
	}
	return 0;
}

总而言之，求质数的常见问题也就写个函数判断或者打表了，看之后的具体题目具体分析那种方法
函数适合那种数据小 问题只问几个数是不是质数，那就没必要打表了
打表就是那种上十万的题目，用函数一个一个判断很容易超时