有很多与数字相关的题目,主要考察基本的编程能力,如果数学比较好,对于解决这些问题有比较好的帮助。下面的题目是学生收集的题目,我进行了讲解。
1、Self Numbers
Description
In 1949 the Indian mathematician D.R. Kaprekar discovered a class of numbers called self-numbers. For any positive integer n, define d(n) to be n plus the sum of the digits of n. (The d stands for digitadition, a term coined by Kaprekar.) For example, d(75) = 75 + 7 + 5 = 87. Given any positive integer n as a starting point, you can construct the infinite increasing sequence of integers n, d(n), d(d(n)), d(d(d(n))), .... For example, if you start with 33, the next number is 33 + 3 + 3 = 39, the next is 39 + 3 + 9 = 51, the next is 51 + 5 + 1 = 57, and so you generate the sequence 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ... The number n is called a generator of d(n). In the sequence above, 33 is a generator of 39, 39 is a generator of 51, 51 is a generator of 57, and so on. Some numbers have more than one generator: for example, 101 has two generators, 91 and 100. A number with no generators is a self-number. There are thirteen self-numbers less than 100: 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, and 97.
Input
No input for this problem.
Output
Write a program to output all positive self-numbers less than 10000 in increasing order, one per line.
Sample Input
Sample Output
1
3
5
7
9
20
31
42
53
64
|
| <-- a lot more numbers
|
9903
9914
9925
9927
9938
9949
9960
9971
9982
9993
题目翻译:有这样的公式y=d(x1x2…xn)=x1+x2+…+xn+ x1x2…xn,例如:
d(123) = 123+1+2+3=129
d(55)=55+5+5=65
这里把x1x2…xn称为y的生成子,例如123是129的生成子,55是65的生成子。题目要求列出10000以内没有生成子的整数。
题目详解:对1到10000的生成子进行遍历,看能够生成哪些数字,然后把不能生成的输出即可,下面的代码供参考。
public static void setNumbers(){
int[] numbers=new int[10000];
Arrays.fill(numbers, 0);
for(int i=1;i<10000;i++){
int temp = i+i%10+(i/10)%10+(i/100)%10+i/1000;
if(temp<10000)
numbers[temp-1]=1;
}
for(int i=0;i<9999;i++){
if(numbers[i]==0)
System.out.println(i+1);
}
}
2、Goldbach's Conjecture
Description
In 1742, Christian Goldbach, a German amateur mathematician, sent a letter to Leonhard Euler in which he made the following conjecture:
Every even number greater than 4 can be written as the sum of two odd prime numbers.
For example:
8 = 3 + 5. Both 3 and 5 are odd prime numbers.
20 = 3 + 17 = 7 + 13.
42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23.
Today it is still unproven whether the conjecture is right. (Oh wait, I have the proof of course, but it is too long to write it on the margin of this page.)
Anyway, your task is now to verify Goldbach's conjecture for all even numbers less than a million.
Input
The input will contain one or more test cases.Each test case consists of one even integer n with 6 <= n < 1000000. Input will be terminated by a value of 0 for n.
Output
For each test case, print one line of the form n = a + b, where a and b are odd primes. Numbers and operators should be separated by exactly one blank like in the sample output below. If there is more than one pair of odd primes adding up to n, choose the pair where the difference b - a is maximized. If there is no such pair, print a line saying "Goldbach's conjecture is wrong."
Sample Input
8
20
42
0
Sample Output
8 = 3 + 5
20 = 3 + 17
42 = 5 + 37
翻译:据推测大于4的偶数都可以写成两个质数(素数)的和。让我们编写程序进行验证,如果有写出表达式,如果没有则输出“Goldbach's conjecture is wrong.”。如果能够写成的式子多于1个,则写出两个数字差比较大的那对。例如:
42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23
输出42 = 5 + 37即可。因为37-5最大。
题目详解:题目比较简单,只要测试两个数是否为质数即可。下面的代码供参考。
/*
* 8 = 3 + 5
* 20 = 3 + 17
* 42 = 5 + 37
*/
public static void test(int x){
if(6<=x && x < 1000000){
if(x%2!=0){
System.out.println("输入数据不是偶数!");
}else{
boolean b=false;
for(int i=3;i+i<x;i++){
if(isPrime(i) && isPrime(x-i)){
System.out.println(x+" = "+i+" + "+(x-i));
b = true;
break;
}
}
if(!b)
System.out.println("Goldbach's conjecture is wrong.");
}
}else{
System.out.println("输入数据范围不对");
}
}
/*
* 判断某个数是否为质数,如果是返回true
*/
public static boolean isPrime(int x){
for(int i=2;i*i<=x;i++){
if(x%i==0)
return false;
}
return true;
}
3、Sum of Consecutive Prime Numbers
Description
Some positive integers can be represented by a sum of one or more consecutive prime numbers. How many such representations does a given positive integer have? For example, the integer 53 has two representations 5 + 7 + 11 + 13 + 17 and 53. The integer 41 has three representations 2+3+5+7+11+13, 11+13+17, and 41. The integer 3 has only one representation, which is 3. The integer 20 has no such representations. Note that summands must be consecutive prime numbers, so neither 7 + 13 nor 3 + 5 + 5 + 7 is a valid representation for the integer 20. Your mission is to write a program that reports the number of representations for the given positive integer.
Input
The input is a sequence of positive integers each in a separate line. The integers are between 2 and 10 000, inclusive. The end of the input is indicated by a zero.
Output
The output should be composed of lines each corresponding to an input line except the last zero. An output line includes the number of representations for the input integer as the sum of one or more consecutive prime numbers. No other characters should be inserted in the output.
Sample Input
2
3
17
41
20
666
12
53
0
Sample Output
1
1
2
3
0
0
1
2
翻译:有些整数可以表示为多个连续质数的和,例如53 = 5 + 7 + 11 + 13 + 17,有的数字有多中表示方法,例如41可以表示为2+3+5+7+11+13, 11+13+17, and 41。题目要求计算给定的某个数有多少种表示方法。
题目详解:对于给定的某个数,先从2开始,然后找下一个质数,然后累加直到他们的和等于或者大于给定的数,如果等于说明是一组解,如果大于说明不是接,然后找下一个接,直到结束。下面的代码供参考。
/*
* Sum of Consecutive Prime Numbers
*/
public static int test2(int x){
int count=0;
for(int i=2;i+i<x;i++){
int sum = 0;
if(!isPrime(i)){
continue;
}
for(int j=i;j<x;j++){
// 判断是否为质数
if(!isPrime(j))
continue;
sum = sum+j;
// 判断是否满足条件
if(sum>=x){
if(sum==x){
count++;
}
break;
}
}
}
if(isPrime(x))
count++;
return count;
}
/*
* 判断某个数是否为质数,如果是返回true
*/
public static boolean isPrime(int x){
for(int i=2;i*i<=x;i++){
if(x%i==0)
return false;
}
return true;
}
4、Binomial Coefficients
Description
The binomial coefficient C(n, k) has been extensively studied for its importance in combinatorics. Binomial coefficients can be recursively defined as follows:
C(n, 0) = C(n, n) = 1 for all n > 0;
C(n, k) = C(n − 1, k − 1) + C(n − 1, k) for all 0 < k < n.
Given n and k, you are to determine the parity of C(n, k).
Input
The input contains multiple test cases. Each test case consists of a pair of integers n and k (0 ≤ k ≤ n < 231, n > 0) on a separate line.
End of file (EOF) indicates the end of input.
Output
For each test case, output one line containing either a “0
” or a “1
”, which is the remainder of C(n, k) divided by two.
Sample Input
1 1
1 0
2 1
Sample Output
1
1
0
翻译:二项式系数(可能翻译的不好)C(n, k)满足下面的要求:
C(n, 0) = C(n, n) = 1 for all n > 0;
C(n, k) = C(n − 1, k − 1) + C(n − 1, k) for all 0 < k < n.
题目要求根据给定的n和k(0 ≤ k ≤ n < 231, n > 0)计算C(n,k),典型的递归问题。但是如果采用递归,当n的值比较大的时候,会堆栈益处。而上面的表达式应该有相应的公式。如果采用公式计算就会变的简单了。公式自己找吧。
分享到:
相关推荐
acm图论.ppt————电子版_ppt版
acm算法数论详解 很好的数论学习 自己看吧!!!!!!!!!
ACM 模版ACM 模版ACM 模版ACM 模版
ACM数论——ppt(天津大学)ACM数论——ppt(天津大学)
几套 ACM题集,对学C或参赛的都由很大的帮助,大家多做题哦!!
acm数论算法学习资料acm数论算法学习资料acm数论算法学习资料acm数论算法学习资料acm数论算法学习资料acm数论算法学习资料
这个ppt主要介绍蛮力搜索的相关内容,这是我竞赛培训的资料,欢迎大家来下载
ACM---算法数论
几道简单的编程题 我没有积分了 我要下东西
数论是ACMer所必须掌握的知识,所以说学好数学哇!
适合初学者ACM们,能够让大家提高自己的学习技术与水平,十分实用。
ACM数论
本人参加第五届acm省赛准备的有关数论的资料
一-BASIC 3 IO挂 3 快速乘法 3 快速幂 3 进制转换(包括负进制)概念 3 一个数二进制1的个数 3 ...筛可以表示成x^2+(x+1)^2的素数 9 高斯整数环与高斯素数 10 n!中素数y的个数 10 筛1~n的因子个数O(n) 10
本次课程论文,针对ACM比赛中的经典算法,动态规划,进行了详细的讲述,并以ZOJ和POJ上的经典题目为例,讲述了动态规划算法的应用。
hdu ACM 高级程序设计习题集——全文 里面有程序的详细解释
数论是Acm中的重点内容。历年竞赛题目, 一般都有1-2道与数论有密切关系。数论涉及的概念 和算法很多,用途也非常广泛。掌握与数论有关的 方法,是参赛者需要具备的必要技能。
蓝桥杯ACM算法比赛模拟题30天每日训练
ACM+数论常用的模版
数论培训课件,包含数论概念和acm数论题目详解的。