驻马店市网站建设_网站建设公司_需求分析_seo优化

2025年华东师范大学计算机考研复试机试真题

2025年华东师范大学计算机考研复试上机真题

历年华东师范大学计算机考研复试上机真题

历年华东师范大学计算机考研复试机试真题

更多学校题目开源地址：https://gitcode.com/verticallimit1/noobdream

N 诺 DreamJudge 题库：输入 “学校名称” 即可筛选该校历年机试真题，题目均在考纲范围内，按难度自动排序。还可搭配《计算机考研机试攻略》刷题，书中题目可通过题号直接在题库中查找。

整数分解

题目描述

Time Limit: 1000 ms
Memory Limit: 256 mb

给一个正整数n，求将其分解为若干个素数之和的方案数。（1<=n<=1000）
比如7，有三种方案：
（1）7
（2）5+2
（3）3+2+2

输入输出格式

输入描述:

如题

输出描述:

如题

输入输出样例

输入样例#:

7

输出样例#:

3

代码一

1. #include<stdio.h>
2. #include<stdlib.h>
3. #include<memory.h>
4. #include<math.h>
5. int isPrim(int n){
6. if(n==1){return 0;}
7. for(int i=2;i<=(int)sqrt(n);i++){
8. if(n%i==0){return 0;}
9. }
10. return 1;
11. }
12. void solve1967(int* prims, long long dp[169][1001]){//完全背包问题
13. for(int i=1; i<=168; i++){
14. for(int j=1; j<=1000; j++){
15. //不用prims[i];
16. dp[i][j] = dp[i-1][j];
17. //用prims[i]
18. if(j == prims[i]){dp[i][j]++;}
19. if(j > prims[i]){dp[i][j]+=dp[i][j-prims[i]];}
20. }
21. }
22. }
23. int main(){
24. int n,prims[169]={0},len=1;
25. long long dp[169][1001];//用前i个素数组成数字j的方案数
26. for(int i=1;i<=1000;i++){
27. if(isPrim(i)==1){prims[len++]=i;}
28. }
29. solve1967(prims,dp);
30. while(scanf("%d",&n) > 0){
31. printf("%lld\n",dp[168][n]);
32. }
33. }

代码二

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int N = 2e3;
4. vector<int> prm;
5. bool vis[N];
6. void init(){
7. for(int i=2;i*i <= 1000; ++i){
8. if(vis[i]) continue;
9. for(int j=i+i;j<=1000;j+=i){
10. vis[j] = 1;
11. }
12. }
13. for(int i=2;i<=1000;++i) if(!vis[i]) prm.push_back(i);
14. // for(int x:prm) cout << x<<' ';
15. }
16. long long f[N];
17. int main(){
18. init();
19. int n; cin >> n;
20. f[0] = 1;
21. for(int x:prm){
22. for(int i=x;i<=n;++i){
23. f[i] += f[i-x];
24. }
25. }
26. cout << f[n];
27. }

代码三

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main() {
4. int n;
5. cin>>n;
6. vector<int> nums;
7. for(int i = 2;i<=n;i++){
8. int flag = 1;
9. for(int j = 2;j<int(sqrt(i))+1;j++){
10. if(i%j==0){
11. flag = 0;
12. break;
13. }
14. }
15. if(flag == 1)
16. nums.push_back(i);
17. }
18. vector<unsigned long long> dp(n+1,0);
19. dp[0] = 1;
20. for(int i = 0;i<nums.size();i++){
21. for(int j = nums[i];j<=n;j++){
22. dp[j] += dp[j-nums[i]];
23. }
24. }
25. cout<<dp[n]<<endl;
26. }