一些简单的acm题

【人民币问题】

Time Limit:1000MS Memory Limit:10000K

Total Submit:574 Accepted:278

Description

给出任意的人民币(>10元)的整币兑换成5元、2元和1元币值（要求三种币值均有）的方法有多少种。

Input

输入任意的人民币(>10元)的整币100,50,20,10

Output

计算出兑换成5元、2元和1元币值（要求三种币值均有）的方法有多少种Sample Input

50

Sample Output

106

Source

【哥德巴赫曾猜测】

Time Limit:10000MS Memory Limit:65536K

Total Submit:592 Accepted:194

Description

德国数学家哥德巴赫曾猜测：任何大于6的偶数都可以分解成两个素数（素数对）的

和。但有些偶数可以分解成多种素数对的和，如： 10=3+7，10=5+5，即10可以分解成两种不同的素数对。

Input

输入任意的>6的正偶数(<32767)

Output

试求给出的偶数可以分解成多少种不同的素数对（注： A+B与B+A认为是相同素数对）

Sample Input

1234

Sample Output

25

Source

Code:

#include

#include

using namespace std;

int main()

{int n;int z=0;

int f(int);

cin>>n;

for(int i=2;i<=n/2;i++)

{

if(f(i)) {if(f(n-i))

{// cout<

z+=1;

}

}

}

cout<

cout<

return 0;

}

int f(int y)

{int j;

for( j=2;j<=sqrt(y);j++)

if(y%j==0) break;

if(j<=sqrt(y))

return 0;

else

return y;

}

【数列问题】

Time Limit:10000MS Memory Limit:65536K

Total Submit:647 Accepted:312

Description

已知一个数列的前3个数为3，4，5，以后每个数为前3个数的和，编程序求此数列的第N项

Input

输入N(N<=35)

Output

求出第N项的值

Sample Input

28

Sample Output

25527448

Source

代码：

#include

void main()

{int a[35]={3,4,5};

int n,i;

scanf(“%d”,&n);

for(i=3;i<=n;i++)

a[i]=a[i-1]+a[i-2]+a[i-3];

printf(“%d\n”,a[n-1]);

}

【敲七】

Time Limit:10000MS Memory Limit:65536K

Total Submit:502 Accepted:170

Description

输出7和7的倍数，还有包含7的数字例如（17，27，37...70，71，72，73...）

Input

一个整数N。(N不大于30000)

Output

统计出不大于N的与7有关的数字的个数。如20以内与7有关的数为7、14、17共3个。

Sample Input

20

Sample Output

3

Source

/*验证哥德巴赫猜想：任一充分大的偶数，可以用两个素数之和表示，例如：

4 = 2 + 2 6 = 3 + 3 …… 98 = 19 + 79。

程序要求：键盘输入一个偶数x>4，找到两个素数a、b，满足 x=a+b。最后输出此等式

提示

我们先不考虑怎样判断一个数是否为素数，而从整体上对这个问题进行考虑，可以这样做：读入一个偶数n ，将它分成p 和q ，使n = p + q 。怎样分呢？可以令p 从2 开始，每次加1 ，而令q = n - p ，如果p 、q 均为素数，则正为所求，否则令p = p + 1 再试。

其基本算法如下：

1）读入大于3的偶数n。

2）P=1

3）do{

4）p=p+1；q=n-p;

5）p是素数吗？

6）q是素数吗？

7）}while(p、q有一个不是素数)

8）输出n=p+q。

为了判明p、q是否是素数，我们设置两个标志量flagp和flagq，初始值为0，若p

是素数，令flagp=1，若q是素数，令flagq=1，于是第7步变成：