C++基础编程题

算法是编程的核心,而在前期学习C++的过程中,我们都会去做一些最基础的算法编程题,包括智力题、图形题以及数学题等等,这些问题大多用不到比较高深的知识点和结构,主要考察我们将数学思想转化为算法编程实现的一种能力,在这一小节中,我总结了几个实例,用来加深自己对它的认识和理解。

图形题

等腰三角形

  • 要求:

输出打印等腰三角形

  • 源代码实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;

int main()  {
//等腰三角形的输出方法
int m,n;
    cout<<"输入三角形的层数:";
    cin>>m;
    cout<<"等腰三角形的输出图形如下:\n";
    //判断输出的行数
    for (int i=1;i<=m;i++)  {
    //输出*时前面输出空格的个数
        for(int j=1;j<=m-i;j++)     {
            cout<<" ";
        }
    //输出*的个数
    for (int k=1;k<=i*2-1;k++)  {
        cout<<"*";
    }
    cout<<endl;
    }
    return 0;
}
  • 输出结果

九九乘法表

  • 要求:

打印输出九九乘法表

  • 源代码实现
1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>  
using namespace std;  

int main()  {  
    for(int i=1;i<10;i++)   {  
        for(int j=1;j<=i;j++)   {  
            cout<<i<<"*"<<j<<"="<<i*j<<"\t";  
        }  
        cout<<endl;  
    }  
    return 0;  
}
  • 输出结果

空心菱形

  • 要求:

打印输出空心菱形

  • 源代码实现
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
#include <iostream>
using namespace std;

int main()  {
    int i,j,k,n;
    cin>>n;
    //外层负责上金字塔层数
    for (i=1;i<=n;i++)  {
        //用于控制每层第一个*前需要打印的" "数
        for (j=1;j<=n-i;j++)
            cout<<" ";
        //用于确定输出空格和*的位置
        for (k=1;k<=2*i-1;k++)  {  
            if (k==1||k==2*i-1)
                cout<<"*";
            else    
                cout<<" ";
        }
    cout<<endl;
    }
    //下面程序模仿上面的形式,相当于将上面的图形倒转
    //除去第n层,下面的循环次数比上面少了一次(第n层已经被打印)
    for (i=n;i>1;i--)   {
        //确定每一层第一个*前需要打印的" "数
        for (j=0;j<=n-i;j++)
            cout<<" ";
        //确定每一层需要输出空格和*的位置
        for (k=1;k<=2*i-3;k++)  {
            if (k==1||k==2*i-3)
                cout<<"*";
            else    
                cout<<" ";
        }
    cout<<endl;        
    }
}
  • 输出结果

智力题

斐波那契数列

描述:第一项和第二项都是1,其后各项满足:$F_n=F_{n-1}+F_{n-2}$

兔生幼子

  • 问题:

有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第3个月后每个月又生一对兔子,假如兔子都不死,问第9个月的兔子总数为多少?

  • 思路:

根据题意,将每月的兔子总数列出,如下图

月份 一月 二月 三月 四月 五月 六月 七月 八月 九月
对数 1 1 2 3 5 8 13 21 34

根据上图,满足斐波那契数列特点,可知,第九个月时,兔子总数是34对。

源代码实现

  • 解法一

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    #include<iostream>    
    using namespace std;  

    int main()  {  
        int f1=1,f2=1,n;  
        cout<<"第1个月有:"<<f1<<"对"<<endl;  
        cout<<"第2个月有:"<<f2<<"对"<<endl;  
        for(n=2;n<6;n++){  
            f1=f1+f2;  
            f2=f1+f2;  //每个月的对数都等于前两个月对数之和
        cout<<"第"<<2*n-1<<"个月有:"<<f1<<"对"<<endl;  
        cout<<"第"<<2*n<<"个月有:"<<f2<<"对"<<endl;  
        }      
        cout<<endl;  
        return 0;  
    }
  • 解法二:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
  
int fun(int n)  {                
    if (n==1 || n==2)  
        return 1;  
    else  
        return fun(n-1)+fun(n-2);  
}  
int main()  {  
    int month;  
    cout<<"你需要查询第几个月兔子数"<<endl;  
    cin>>month;  
    fun(month);  
    cout<<"第"<<month<<"个月兔子数量为: " <<fun(month)<<"对";
    return 0;  
}

猴子吃桃

  • 问题:

猴子第一天摘下若干个桃子,当即吃了一半,还不瘾,又多吃了一个,第二天早上又将剩下的桃子吃掉一半,又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时,见只剩下一个桃子了。求第一天共摘了多少桃子?

  • 思路:
天数 第一天 第二天 第三天 第八天 第九天
剩余桃子数 x/2-1 x/4-3/2 x/8-7/4 $x_7/2-1$ 1

根据题中规律,第n天,剩余桃子数$x_n=x_{n-1}/2-1$。
现已知第九天剩余1个桃子,向前回溯9天即可推断出第一天一共摘下的桃子数。

  • 源代码实现
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>  
using namespace std;  

int main()  {  
    int n1,n2=1,i;  
    for(i=1;i<10;i++){  //根据规律,需要向前回溯九天,即循环九次
        n1=(n2+1)*2;    //上一天的剩余桃子数等于下一天剩余桃子数加一的2倍
        n2=n1;  
    }  
    cout<<n2<<endl;  
    return 0;  
}

数学题

最大公约数/最小公倍数

  • 问题:

求两数A、B的最大公约数和最小公倍数

  • 思路:
  • 最大公约数时,利用欧几里得算法
    如果B等于0,答案就是A;否则,答案就是gcf(B,A%B)。
  • 最小公倍数时:两数之积除于最大公约数
  • 源代码实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;

int gcf(int a,int b)        {
if        (b==0)
return a;
else
return gcf(b,a%b);
}
int main()        {
int a,b;
while(cin>>a>>b)
cout<<gcf(a,b)<<endl; //求最大公约数
cout<<a*b/gcf(a,b)<<endl; //求最小公倍数
return 0;
}

水仙花问题

  • 描述:

“水仙花数”是指一个三位数,其各位数字立方和等于该数本身。

  • 思路:

学会分解出一个数的各个数位。

  • 源代码实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
	#include<iostream>  
using namespace std;  

int main()  {  
    int i,j,k;
    for (int n=100;n<1000;n++)  {
        i=n/100;        //分解出百位数
        j=n/10%10;      //分解出十位数
        k=n%10;         //分解出个位数
        if (i*100+j*10+k==i*i*i+j*j*j+k*k*k)        //判断成立条件
            cout<<n<<"\t";
    }
    return 0;
}
-------------The End-------------