c++常见的算法快速分析解决(二)

2014-11-24 12:59:09 · 作者: · 浏览: 0

题目:斐波那契数列,FIBONACCI数列特点是第1,第2两个数为1,1.从第3个数开始,该数是前两个数之和,求这个数列的前30个元素
分析: 波那西 列(Fibonacci Sequence),又 波拿契 、斐波那契 列、 氏 列、 金分割 列。在 上, 波那西 列是以 的方法 定 :
F0 = 0
F1 = 1
Fn = Fn- 1 + Fn - 2
用文字 ,就是 波那西 列由 0 和 1 始,之後的 波那西 就由之前的 相加。首 波那西 是(OEIS A000045):
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,
4181, 6765, 10946,………………
特 指出:0不是第一 ,而是第零 。(参考)
分析题目我们可以用如下等式来表示斐波那契数列:
F1=1----(n=1);
F2=1----(n=1);
Fn=F(n-1)+F(n-2)-----(n>=3)
这里我们将F的下标看成是数组的下标代码如下:
#include#includeint main(){ int i;/*定义整形变量*/ long f[31];/*定义数组为长整形*/ f[1]=f[2]=1;/*数组的f[1],f[2]赋值为1*/ for(int i=3;i<31;i++) { f[i]=f[i-1]+f[i-2];/*数组从第三行开始,每一项等于前两项之和*/ } for(i=1;i<31;i++) { printf("%10ld",f[i]);/*输出数组中的30个元素*/ if(i%5==0) printf(" ");/*每5个元素进行一次换行*/ } system("PAUSE"); }

结果:


题目:角谷猜想 ,任意一个自然数,当他为偶数的时候则除以2,当他为奇数的时候则乘3加1,得到一个新的自然数,依次按照这个法则继续演算,到很多次以后,就会得到一个结果,这个结果是1...
分析:考拉兹猜想,又称为3n+1猜想、冰雹猜想、角谷猜想、哈塞猜想、乌拉姆猜想或叙拉古猜想,是指对于每一个正整数,如果它是奇数,则对它乘3再加1,如果它是偶数,则对它除以2,如此循环,最终都能够得到1。(维基百科)
有题目分析可知,重点是判断一个数是奇数还是偶数,程序采用对2取余的方法,当余数为0时,说明该数为偶数,否则为奇数
举例:取一个数字

如n = 6,根据上述数式,得出 6→3→10→5→16→8→4→2→1 。(步 中最高的 是16,共有7 步 )

如n = 11,根据上述数式,得出 11→34→17→52→26→13→40→20→10→5→16→8→4→2→1。(步 中最高的 是40,共有13 步 )

如n = 27,根据上述数式,得出 : 27→82→41→124→62→31→94→47→142→71→214→107→322→161→484→242→121→364→182→91→274→137→412→206→103→310→155→466→233

→700→350→175→526→263→790→395→1186→593→1780→890→445→1336→668→334→167→502→251→754→377→1132→566→283→850→425→1276

→638→319→958→479→1438→719→2158→1079→3238→1619→4858→2429→7288→3644→1822→911→2734→1367→4102→2051→6154→3077→9232

→4616→2308→1154→577→1732→866→433→1300→650→325→976→488→244→122→61→184→92→46→23→70→35→106→53→160→80→40→20→10

→5→16→8→4→2→1。(步 中最高的 是9232,共有111 步 )

考拉兹猜想称,任何正整数,经过上述计算步骤後,最终都会得到 1 。代码:
#include#includevoid main(){ long i,n; //定义变量为长整形 printf("please input a number: ");//输入任意一个长整形数 scanf("%ld",&n); while(n!=1) { if(n%2==0) //判断是否为偶数 { printf("%ld/2=%ld ",n,n/2);//当为偶数的时候n除以2 n=n/2; } else { printf("%ld*3+1=%ld ",n,n*3+1);//当我奇数时乘以3加1 n=n*3+1; } } system("pause");}

结果:


题目:歌德巴赫猜想,验证100以内的的正偶数都能分解为两个素数之和
分析:任一大於2的偶 ,都可表示成 之和。
一 定的偶 表示成 之和被 之 此 的哥德巴赫分割。例如,
4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 3 + 7 = 5 + 5
12 = 5 + 7
14 = 3 + 11 = 7 + 7

句 ,哥德巴赫猜想主 每 大於等於4的偶 都是哥德巴赫 -可表示成 之和的 [1]。哥德巴赫猜想也是希 伯特第八 中的一 子 。
另有 奇 的相似猜想, 之 勒穆瓦纳猜想(Lemoines conjecture)或李 猜想(Levys conjecture)。
为了验证哥德巴赫猜想对100以内的正偶数成立,所以要将正偶数分为两部分,在对这两部分进行判断,如果均是素数则满足体艺,不是的话,则重新分解继续判断代码:
#include#include int ss(int i)/*自定义一个函数是不是素数*/ { int j; if(i<=1)/*小于1的不是素数*/ return 0; if(i==2) /*2是素数*/ return 1; for(j=2;j

题目:四方定理,所有的自然数至多只要4个数的平方和就可以表示,编程验证
可以采用穷举试探的方法进行计算,当满足定理的条件就可以输出结果
代码:
#include#includeint main(){ long i,j,k,l,n;//定义变量为长整形 printf("请输入 一个长整形的整数"); scanf("%ld",&n); for(i=0;i