当前位置:首页 >> 工学 >> ACM程序设计-计算简单题

ACM程序设计-计算简单题


ACM程序设计 ACM程序设计
简单计 题

列出完数
题目内容
自然数中,完数寥若晨星,请在从 到某个整数范围 自然数中,完数寥若晨星,请在从1到某个整数范围 中打印出所有的完数来。所谓“完数” 中打印出所有的完数来。所谓“完数”是指一个数 恰好等于它的所有不同因子之和。例如, 是完数 是完数, 恰好等于它的所有不同因子之和。例如,6是完数, 因为6=1+2+3。而24不是完数,因为 不是完数, 因为 。 不是完数 24 ≠1+2+3+4+6+8+12(=36)。 。

输入描述
输入数据中含有一些整数n(1<n<10000) 输入数据中含有一些整数

2/31

输出描述
对于每个整数n,输出所有不大于 的完数 的完数。 对于每个整数 ,输出所有不大于n的完数。每个整 的输出由n引导 数n的输出由 引导,跟上冒号,然后是由空格开道 的输出由 引导,跟上冒号, 的一个个完数,每个n的完数列表应占独立的一行 的完数列表应占独立的一行。 的一个个完数,每个 的完数列表应占独立的一行。

输入样例 100 5000 输出样例 100: 6 28 : 5000: 6 28 496 :
3/31

题目分析
如果针对每个整数都搜索一次 完数,时间会花费较多, 完数,时间会花费较多,由于 完数较少,可以先找出10000 完数较少,可以先找出 以内的所有完数, 以内的所有完数,然后再针对 n查表。 查表。 查表

4/31

参考源代码
#include <stdio.h> int main(void) { int i,j,k=0,n,sum,a[100]; for(i=2;i<10000;i+=2) //已知完数为偶数 已知完数为偶数 { sum=1; for(j=2;j<=i/2;j++) { if(i%j==0) sum+=j; } if(sum==i) a[k++]=i; }
5/31

参考源代码
while(scanf("%d",&n)==1) { printf("%d: ",n); for(i=0;i<k;i++) { if(a[i]<=n) printf("%d ",a[i]); } printf("\n"); } return 0; }
6/31

对称三位数素数
题目内容
判断一个数是否为对称三位数素数。所谓“对称” 判断一个数是否为对称三位数素数。所谓“对称” 是指一个数,倒过来还是该数。例如, 不是对称 是指一个数,倒过来还是该数。例如,375不是对称 因为倒过来变成了573。 数,因为倒过来变成了 。

输入描述
输入数据含有不多于50个的正整数 输入数据含有不多于 个的正整数(0<n<2^32)。 个的正整数 。

输出描述
对于每个n,如果该数是对称三位数素数, 对于每个 ,如果该数是对称三位数素数,则输出 “Yes”,否则输出“No”。每个判断结果单独一行。 ,否则输出“ 。每个判断结果单独一行。

7/31

输入样例 11 101 272 输出样例 No Yes No

8/31

题目分析

三位对称只须判断个数与百位 是否相等。 是否相等。

9/31

参考源代码
#include <stdio.h> #include <math.h> int isprime(int a) { int i; int s=(int)sqrt((double)a); for(i=2;i<=s;i++) { if(a%i==0) return 0; } return 1; }
10/31

参考源代码
int main(void) { int n; while(scanf("%d",&n)==1) { printf("%s",(n>100&&n<1000 &&n/100==n%10 &&isprime(n)) ?"Yes\n":"No\n"); } return 0; }
11/31

五位以内的对称素数
题目内容
判断一个数是否为对称且不大于五位数的素数。 判断一个数是否为对称且不大于五位数的素数。

输入描述
输入数据含有不多于50个的正整数 输入数据含有不多于 个的正整数n(0<n<2^32)。 个的正整数 。

输出描述
对于每个n,如果该数是不大于五位数的对称素数, 对于每个 ,如果该数是不大于五位数的对称素数, 则输出“ 则输出“Yes”,否则输出“No”。每个判断结果单 ,否则输出“ 。 独列一行。 独列一行。

12/31

输入样例 11 101 272 输出样例 Yes Yes No

13/31

题目分析

怎样判断每位对称素数? 怎样判断每位对称素数?

14/31

参考源代码
#include <stdio.h> int isprime(int n) { int i; if(n==1) //1不是素数 不是素数 return 0; if(n!=2&&n%2==0)//除开 以外的偶数 除开2以外的偶数 除开 return 0; for(i=3;i*i<=n;i+=2)//恰好跳过 恰好跳过2,3,5,7,它们是素数 恰好跳过 , { if(n%i==0) return 0; } return 1; }
15/31

int issym(int n) { if(n<12&&n!=10)//1位是对称数,2位素数中只有 是对称的 位是对称数, 位素数中只有 位素数中只有11是对称的 位是对称数 return 1; if(n>100&&n<1000&&n/100==n%10)//3位数中只须个位与 位数中只须个位与 百位相等 return 1; //注意四位数不可能有对称的素数,易得有 因子 注意四位数不可能有对称的素数, 注意四位数不可能有对称的素数 易得有11因子 if(n>10000&&n/1000==n%10*10+n/10%10) return 1; return 0; }

参考源代码

16/31

参考源代码
int main(void) { int n; while(scanf("%d",&n)==1) { printf("%s\n",n<100000&&issym(n) &&isprime(n)?"Yes":"No"); } return 0; }
17/31

An easy problem
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

18/31

Problem Description
When Teddy was a child , he was always thinking about some simple math problems ,such as “What it’s 1 cup of water plus 1 pile of dough ..” , “100 yuan buy 100 pig” .etc.. One day Teddy met a old man in his dream , in that dream the man whose name was“RuLai” gave Teddy a problem : Given an N , can you calculate how many ways to write N as i * j + i + j (0 < i <= j) ? Teddy found the answer when N was less than 10…but if N get bigger , he found it was too difficult for him to solve. Well , you clever ACMers ,could you help little Teddy to solve this problem and let him have a good dream ?
19/31

Input The first line contain a T(T <= 2000) . followed by T lines ,each line contain an integer N (0<=N <= 1010 ). Output For each case, output the number of ways in one line.

20/31

Sample input: 2 1 3 Sample output: 0 1

21/31

题目分析: 题目分析:
思路1 思路1: 将等式变形为 N + 1 = (i + 1) * (j + 1), , 由于i 由于 <= j,只需要枚举 (枚举范围从 ,只需要枚举i 枚举范围从1 ),然后判断是否满足 然后判断是否满足, 到 N ),然后判断是否满足,直接计数 即可。 即可。

22/31

思路2 思路2:
同样将等式变形N 同样将等式变形 + 1 = (i + 1) * (j + 1)。只 。 需要求出N 的约数个数, 需要求出 + 1的约数个数,然后分情况处理即 的约数个数 的约数个数为f[N + 1] 可。令N + 1的约数个数为 的约数个数为 1. 当N + 1为完全平方数时,ans = (f[N + 1] – 为完全平方数时, 为完全平方数时 2 + 1) / 2 公式可以理解成:所有的约数,去掉 和本身 公式可以理解成:所有的约数,去掉1和本身 之后( ),剩下的可以对称的组成一对一 之后(减2),剩下的可以对称的组成一对一 ), 对的答案。 对的答案。
23/31

2. 当N +1非完全平方数,同理可得, 1非完全平方数,同理可得, ans = (f[N + 1] – 2) / 2 。 如何快速的求一个数N的约数个数 如何快速的求一个数 的约数个数 我们知道,任何一个自然数 可以表示成其质因数 我们知道 任何一个自然数N可以表示成其质因数 任何一个自然数 的幂的乘积的形式. 的幂的乘积的形式 a1 a2 an 1 2 n

N= p ×p

× ...... × p

由排列组合的乘法原理知, 的约数个数 由排列组合的乘法原理知,N的约数个数 f[N] = (a1 + 1) * (a2 + 1)*…*(an + 1) 而分解质因数最有效的方法就是筛出 而分解质因数最有效的方法就是筛出105范围内的 素数表,然后依次试除。 素数表,然后依次试除。
24/31

1、简单的筛素数 、

其思想是,先假定所有的数都是素数, 其思想是,先假定所有的数都是素数, 然后从2开始依次筛掉素数的倍数的数 开始依次筛掉素数的倍数的数。 然后从 开始依次筛掉素数的倍数的数。

25/31

const int Max = 100000; bool bp[Max + 1]; //记录每个数是否是素数 记录每个数是否是素数 int p[30000]; //记录筛选出来的素数 记录筛选出来的素数 int pCnt=0; //记录当前筛选出来的素数个数 记录当前筛选出来的素数个数 void sievePrime() { int i, j; memset(bp, true, sizeof(bp)); bp[0] = bp[1] = false; for (i = 2; i <= Max; i++) { if (bp[i]) //i是素数 是素数 { p[pCnt++] = i; for (j = i + i; j <= Max; j += i) //依次筛掉 的倍数 依次筛掉i的倍数 依次筛掉 bp[j] = false; } } }

26/31


更多相关文档:

第六届ACM程序设计大赛决赛试题

第六届ACM程序设计大赛决赛试题_IT/计算机_专业资料...(A)---中北大学 2011-03-11 15:31 A-简单排序...且所需计算的数字的个数 n 的范围: 1<=n<=15...

《ACM算法与程序设计》解题报告模板

杭电ACM题题目及代码 75页 免费如要投诉违规内容...《ACM算法与程序设计》解题报告模板《ACM算法与程序设计...过程中要 反复使用,它的效率成为决定整个计算效率的...

历届程序设计acm试题

历届程序设计acm试题_工学_高等教育_教育专区。搜集...否则第二行输出你计算出的最远距离,第三行输出跟...游戏的规则很简单, 首先将纸牌中的大、 小王取出;...

ACM程序设计综合实践

的进一步的理解与巩固,是将计 算机课程与实际问题...建立简单的数学模型,求出游客需要房间数和所住天数,...acm编程比赛入门题目 25页 1下载券 ACM程序设计(...

ACM算法与程序设计--高精度计算

杨鹏 【摘要】本文作为 ACM 算法与程序设计素质教育选修课的报告,主要叙述了怎样进行高精度计算, 对于解答高精度计算题目时遇到的一些问题和分析,以及一些个人心得与...

ACM程序设计竞赛例题[1]

ACM程序设计竞赛例题[1]_理学_高等教育_教育专区。备战 ACM 资料 习题 1. 0...[n]; } 由于每个数组单元的计算耗费Ο (1)时间,算法 lcs_length 耗时Ο (...

ACM程序设计入门 考试题目

ACM 程序设计入门》 考试题目 考试说明: 考试说明: 考试形式:提交 A4 纸双面手写报告 成绩评定: 及格:交规范解题报告,并正确解题 报告雷同;不交报告; 不及格...

ACM算法设计实验题目汇总

ACM 算法设计实验题目汇总 1020 Permutation with ...编程任务: 对于给定的 k 个待安排的活动,编程计算...cs3简单制作动态搞笑图片 160份文档 2014年度细分行业...

ACM程序设计题目

ACM大赛试题ACM大赛试题隐藏>> ACM 程序设计题目 2006-08-08 15:38 1. 给定...请计算画 完这三个圆所需的最小时间。 输入格式为: 第一行为一个正整数 T...

acm程序设计模板(全)

ACM程序设计 4页 1下载券 ACM程序设计 65页 7下载券 ACM程序设计题目 2页 ...(s3,s1,l1,l2,s2); } //计算两直线交点,注意事先判断直线是否共面和平行...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com