本文主要是介绍《算法分析与设计》练习14，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

目录

A 菱形图案

B 牛妹的蛋糕

C 尼科彻斯定理

D ABC+DEF=GHI

 E  油田问题

 F 马的遍历问题

A 菱形图案

题目描述

KiKi学习了循环，BoBo老师给他出了一系列打印图案的练习，该任务是打印用“*”组成的菱形图案。

输入

多组输入，一个整数（2~20）。

输出

针对每行输入，输出用“*”组成的菱形，每个“*”后面有一个空格。每输出一个菱形的后面需要空一行。

样例输入 Copy

2

3

4

样例输出 Copy

*

* *

* * *

* *

*

*

* *

* * *

* * * *

* * *

* *

*

*

* *

* * *

* * * *

* * * * *

* * * *

* * *

* *

*

分析：这题还是比较简单，就是一个凑一凑规律的问题，认真的话，一般都写的出来。

理清 * 和 空格之间的 关系。

很显然，分两步走， 先输出 空格  ，  再  输出 '*  '（*加 空格）。

这个我也就不哆嗦了，直接看代码理解即可。

代码实现：c语言

#include <stdio.h>

#include <stdlib.h>



int main (){



int n;

while(~scanf("%d",&n)){

    solve (n);

    printf("\n");

}

return 0;

}

void solve (int n){

for(int i=0;i<=n;i++)

{

     for(int j=0;j<n-i;j++)

            printf(" ");

     for(int j=0;j<=i;j++)

        printf("* ");

       printf("\n");



}

for(int i=n-1;i>=0;i--)

{

    for(int j=0;j<n-i;j++)

        printf(" ");

    for(int j=0;j<=i;j++)

        printf("* ");

    printf("\n");



}

}

B 牛妹的蛋糕

题目描述

众所周知，牛妹非常喜欢吃蛋糕。

第一天牛妹吃掉蛋糕总数三分之一多一个，第二天又将剩下的蛋糕吃掉三分之一多一个，以后每天吃掉前一天剩下的三分之一多一个，到第n天准备吃的时候只剩下一个蛋糕。

牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？

输入

输入n，0<n< 30。

输出

输出第一天蛋糕的数量。

样例输入 Copy

2

4

样例输出 Copy

3

10

分析：找规律而已，设前 一天的 蛋糕为 x，那么这一天的 剩下的蛋糕 则为  2/3 *x-1;  

那么 我们就从后往前推即可，从1 开始， （1 +1）*3/2;

代码实现：c语言

#include <stdio.h>

#include <stdlib.h>



int main (){

int n;



while(~scanf("%d",&n)){

        int x=1;

    for(int i=1;i<n;i++)

      x=(x+1)*3/2;

    printf("%d",x);

    printf("\n");

    x=0;

}

return 0;

}

C 尼科彻斯定理

题目描述

验证尼科彻斯定理，即：任何一个整数m的立方都可以写成m个连续奇数之和。

例如：

1^3=1

2^3=3+5

3^3=7+9+11

4^3=13+15+17+19

输入

多组输入，输入一个整数。

输出

输出分解后的字符串。

样例输入 Copy

6

样例输出 Copy

31+33+35+37+39+41

分析：这个题还是找规律的题；之前还想着 左边立方，右边  sum相加，然后循环，如果相等就输出。

后面发现还有一个更加靠谱的规律。

就是，先把这个数 平方， 然后  一个循环 ok，第一个要输出的数总是 等于这个平方数 - n +1；

不管是n是偶数还是奇数，都一样。然后就可以  跟着循环加 2 即可。

代码实现：c语言

#include <stdio.h>

#include <stdlib.h>

#include <math.h>



int main (){



int n;

while(~scanf("%d",&n)){

    int a[n];

    int z=solve(a,n);

}





return 0;

}



int solve (int a[],int n){

int lfs=n*n*n;

int sum=0;

int pfs=n*n;

    for(int i=0;i<n;i++)

         a[i]=pfs-n+1+i*2;



for(int i=0;i<n-1;i++)

    printf("%d+",a[i]);

    printf("%d",a[n-1]);

printf("\n");

}

D ABC+DEF=GHI

题目描述

用1, 2, 3...9 这九个数字组成一个数学公式，满足：ABC + DEF = GHI，每个数字只能出现一次，编写程序输出所有的组合。

输入

无

输出

输出所有的 ABC + DEF = GHI，

每行一条数据，格式为ABC+DEF=GHI

输出结果按照ABC升序排列，如果ABC相同，则按照DEF升序排列。

分析：这道题我沿用了之前学过的  九数组分数问题，形式是一样滴。

代码实现：c语言

#include <stdio.h>

#include <stdlib.h>

int a[9];

int v[9];

int main (){

   digui(1);

return 0;

}



void digui (int k){

if(k==10) {

    if((a[1]*1000+a[2]*100+a[3]*10+a[4])*3 == a[5]*10000+a[6]*1000+a[7]*100+a[8]*10+a[9] ){

            printf("%d%d%d%d/%d%d%d%d%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);

            return ;

            }

}

else{

    for(int i=1;i<=9;i++)

    {

        if(v[i]==0){

              a[k]=i;

              v[i]=1;

        digui(k+1);

        v[i]=0;

        }

    }

}

}

 E  油田问题

题目描述

输入一个m行n列的字符矩阵，统计字符“@”组成多少个八连块。如果两个字符“@”所在的格子相邻（横、竖或者对角线方向），即属于同一个八连块。

输入

多组输入

输入行数m，以及列数n。

然后输入*和@

1<=n,m<=100

输出

联通块个数

样例输入 Copy

5 5

****@

*@@*@

*@**@

@@@*@

@@**@

样例输出 Copy

2

分析：回溯法其实就是递归，像油田问题，完全就是递归当中加了个 剪枝函数。

这个呢，其实你看代码手动  画一画递归树就更加清晰。

剪枝呢？一个是 看它出没有出界， 二个呢  就是  在它是@ 的条件下，是否被标记。

接下来  就是 循环  递归  八方找同类的@。

具体看代码分析：

代码实现：c语言

#include <stdio.h>

#include <stdlib.h>



char pic[200][200];

int idx[200][200];

int count=0;

int n;

int m;

int main (){



while(~scanf("%d %d",&m,&n)){

    for(int i=0;i<m;i++)

         scanf("%s",pic[i]);



    for(int i=0;i<m;i++)

        for(int j=0;j<n;j++)

    {

        if(idx[i][j]==0&&pic[i][j]=='@') solve(i,j,++count);

    }

        printf("%d",count);

    printf("\n");

    count=0;

    for(int i=0;i<m;i++)

        for(int j=0;j<n;j++)

        idx[i][j]=0;

}





return 0;

}





void solve (int r,int c,int id){

if(r<0||r>=m||c<0||c>=n) return;

if(idx[r][c]>0||pic[r][c]!='@') return;

idx[r][c]=id;

for(int i=-1;i<=1;i++)

    for(int j=-1;j<=1;j++)

         if(i!=0||j!=0) solve(r+i,c+j,id);



}

 F 马的遍历问题

题目描述

在5*4的棋盘中，马只能走斜“日”字。马从位置(x, y)处出发，把棋盘的每一格都走一次，且只走一次，请找出所有路径。

输入

x,y，表示马的初始位置。

输出

将每一格都走一次的路径总数，如果不存在该路径则输出“No solution!”。

样例输入 Copy

1 1

2 2

样例输出 Copy

32

No solution!

分析：这道题，怎么讲呢，像这种 回溯题，都是可以用来 通解的。

都是可以画递归树来理解的，所以多说无益，还是要自己看代码分析画一画。

方法呢，就是 剪枝函数，只要是被标记的或者是 出界的通通剪掉。

再就是  八个位置的 递归，一旦 把所有格子都走到了，就可以对解的个数加1。

代码实现：c语言

#include <stdio.h>

#include <stdlib.h>

int A[200][200];

int n=5;

int m=4;

int count=0;

int fx[8]={1,2,2,1,-1,-2,-2,-1};

int fy[8]={2,1,-1,-2,-2,-1,1,2};





int main (){

    int x;

    int y;



while(~scanf("%d %d",&x,&y)){

    solve(x,y,1);

    if(count!=0)

    printf("%d",count);

    else{

        printf("No solution!");

    }

    printf("\n");

    count=0;

}



return 0;

}



void solve(int x,int y,int step){

    int nextx;

    int nexty;

A[x][y]=step;

if(n*m==step) count++;

for(int i=0;i<=7;i++)

    {

        nextx=x+fx[i];

        nexty=y+fy[i];

        if(check(nextx,nexty))

            solve(nextx,nexty,step+1);

    }

    A[x][y]=0;

}

int check(int x,int y){

if(x>=1&&x<=n&&y>=1&&y<=m&&A[x][y]==0)

    return 1;

else return 0;

}

这篇关于《算法分析与设计》练习14的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！