经典编程题解

一、(斐波那契数列,又称黄金分割数列,指的是这样一个数列: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

上一篇:操作系统面试之一——程序、进程、线程


下一篇:IOS设计模式第三篇之外观设计模式