一、（斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）。特别指出：第0项是0，第1项是第一个1。这个数列从第二项开始，每一项都等于前两项之和。）
1、有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第10级台阶有几种不同的走法?
解：这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种登法……
1，2，3，5，8，13……所以，登上十级，有89种走法。
2、一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？
解：依次类推可以列出下表：
编程实现：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#include <stdio.h>
void
main()
{
int
s1, s2, s, i;
s1=1;
s2=1;
printf
(
"%d\n%d\n"
, s1, s2);
for
(i=0; i<20; i++)
{
s = s1 + s2;
s1 = s2;
s2 = s;
printf
(
"%d\n"
,s);
}
}
|
二、（约瑟夫环问题(Josephus)
1、用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。写出C程序。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
#include <iostream>
using
namespace
std;
typedef
struct
RingNode {
int
pos;
//位置
struct
RingNode *next;
}RingNode;
//创建循环链表
RingNode *CreateRing(RingNode *head,
int
count)
//count表示节点个数
{
int
i=1;
RingNode *cur, *pre;
head = (RingNode *)
malloc
(
sizeof
(RingNode));
head->pos = 1;
head->next = NULL;
pre = head;
while
(--count > 0)
{
cur = (RingNode *)
malloc
(
sizeof
(RingNode));
cur->pos = ++i;
pre->next = cur;
pre = cur;
}
cur->next = head;
return
head;
}
void
Josephus(RingNode *head,
int
number)
{
int
i=1;
RingNode *cur, *pre;
cur = pre = head;
while
(cur != NULL)
{
if
(i == number)
{
//踢出环
cout<<cur->pos<<
" "
;
pre->next = cur->next;
free
(cur);
cur = pre->next;
i=1;
}
pre = cur;
cur = cur->next;
if
(pre == cur)
{
cout<<endl<<
"最后留下的为:"
<<cur->pos<<endl;
free
(cur);
break
;
}
i++;
}
}
//打印循环链表
void
PrintRing(RingNode *head)
{
cout<<
"链表为："
<<endl;
RingNode *cur;
cout<<head->pos<<endl;
cur = head->next;
while
(cur != NULL)
{
if
(cur->pos == 1)
break
;
cout<<cur->pos<<endl;
cur = cur->next;
}
}
int
main()
{
int
m, n;
RingNode *head=NULL;
cin>>m;
//报到要退出的数
cin>>n;
//人数
head = CreateRing(head, n);
PrintRing(head);
Josephus(head, m);
return
0;
}
|
2、无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm），当n，m非常大（例如上百万，上千万）的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。
为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1）），从0开始报数，报到（m-1）的退出，剩下的人继续从0开始报数。求胜利者的编号。
我们知道第一个人（编号一定是（m-1） mod n) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m mod n的人开始）：
k k+1 k+2 ... n-2,n-1,0,1,2,... k-2
并且从k开始报0。
我们把他们的编号做一下转换：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
变换后就完完全全成为了（n-1）个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k) mod n
如何知道（n-1）个人报数的问题的解？对，只要知道（n-2）个人的解就行了。（n-2）个人的解呢？当然是先求（n-3）的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：
令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]
递推公式
f[1]=0;
f=(f+m) mod i; (i>1）
有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1
由于是逐级递推，不需要保存每个f，程序也是异常简单：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
#include <iostream>
using
namespace
std;
int
main()
{
int
n, m, i, s=0;
cin>>m;
cin>>n;
for
(i=2; i<=n; i++)
s = (s + m) % i;
cout<<
"最后留下的为："
<<s+1<<endl;
return
0;
}
|
1、打靶
一个射击运动员打靶，靶一共有10环，连开10枪打中90环的可能性有多少种？请用递归算法实现。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include <iostream>
using
namespace
std;
int
sum;
int
store[10];
//打印符合要求的每次环数
void
Output()
{
for
(
int
i = 9; i>=0; i--)
cout<<store[i]<<
" "
;
cout<<endl;
++sum;
}
void
Cumput(
int
score,
int
num)
{
/*如果总的成绩超过了90环（也就是score<0），或者如果剩下要打靶的成绩大于10环乘以剩下要打的次数，
也就是说即便后面的都打10环也无法打够次数，则退出递归。*/
if
(score<0 || score > (num+1)*10)
//次数num为0 ~ 9
return
;
//如果达到条件且达到最后一层
if
(num == 0)
{
store[num] = score;
Output();
return
;
}
for
(
int
i=0; i<=10; i++) {
store[num] = i;
Cumput(score - i, num - 1);
}
}
int
main(
int
argc,
const
char
* argv[]) {
Cumput(90, 9);
cout<<
"总数: "
<<sum<<endl;
return
0;
}
//输出：92378
|
2、请编写一个函数，把字符串中的所有字符子串的各种组合形式全部显示出来。字符子串的长度范围是从一个字符到字符串的长度。不管排列顺序如何，只要两种组合中的字符完全一样，它们就是同一种组合。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <iostream>
using
namespace
std;
int
sum=0;
char
str[] =
"hart"
;
int
length;
char
*out;
void
DoCombien(
char
in[],
char
out[],
int
length,
int
rec,
int
start)
{
int
i;
for
(i = start; i < length; i++)
{
out[rec] = in[i];
out[rec+1] = 0;
cout<<out<<endl;
if
(i < length-1)
DoCombien(in, out, length, rec+1, i+1);
}
}
int
main(
int
argc,
const
char
* argv[])
{
length =
strlen
(str);
out = (
char
*)
malloc
(length+1);
DoCombien(str, out, length, 0, 0);
return
0;
}
/*输出：
h
ha
har
hart
hat
hr
hrt
ht
a
ar
art
at
r
rt
t
*/
|
3、求100以内的素数。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include<iostream>
#include<cmath>
using
namespace
std;
int
main()
{
int
i, j;
for
(i=2; i<=100; i++)
{
for
(j=2; j<=
sqrt
(i); j++)
{
if
(i%j == 0)
break
;
}
if
(j>
sqrt
(i))
cout<<i<<endl;
}
return
0;
}
|
4、利用筛选法查找100以内的素数。
解析：所谓筛选法是指从小到大筛去一个已知素数的所有倍数。例如，根据2我们可以筛去4、6、8、......、98、100等数，然后根据3可以筛去9、15、......、99等数（注意此时6、12等数早就被筛去了），由于4被筛去了，下一个用于筛选的素数是5......依次类推，最后剩下的就是100以内的素数。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include<iostream>
using
namespace
std;
int
main()
{
int
a[101], i, j;
for
(i=1; i<=100; i++)
a[i]=1;
for
(i=2; i<=100; i++)
{
if
(a[i]!=0)
{
for
(j=i+i; j<=100; )
{
if
(j%i == 0)
a[j]=0;
j=j+i;
}
}
}
for
(i=2; i<=100; i++)
if
(a[i]!=0)
cout<<i<<
" "
;
return
0;
}
|
5、写出下面程序的运行结果：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <stdio.h>
#include <stdlib.h>
#define LOOP 1000
int
main()
{
int
i=0;
for
(
int
j=0; j<LOOP; j++)
{
int
x=
rand
();
int
y=
rand
();
if
(x*x+y*y < RAND_MAX*RAND_MAX)
i++;
}
printf
(
"%d\n"
, i);
return
0;
}
|
输出：778.
解析：该程序实际是求一个1/4圆面积与一个正方形面积之比。
6、 给出一个单链表，不知道节点N的值，怎样只遍历一次就可以求出中间节点，写出算法。
解析：设立两个指针，比如*p1和*p2，p1每次移动两个位置，p2每次移动一个位置，当p1到达最后一个节点时，p2就是中间节点了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
node *searchmid(node *head)
{
node *p1, *p2, *mid;
p1 = head;
p2 = head;
while
(p1->next != NULL)
{
p1 = p1->next->next;
p2 = p2->next;
mid = p2;
}
cout<<mid->data<<endl;
return
mid;
}
|
7、分解质因数：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#include <stdio.h>
void
main( )
{
int
data, i = 2;
scanf
(
"%d"
, &data);
while
(data > 1)
{
if
(data % i == 0)
{
printf
(
"%d "
, i);
data /= i;
}
else
i++;
}
}
|
8、判断闰年：
|
1
2
3
|
if
((n%4==0 && n%100!=0)||(n%400==0))
//如果是闰年
if
(n.month > 2)
//如果月份大于2
days++;
//总天数加1
|
