2022年春季学期《算法分析与设计》练习14

目录

打印菱形 

问题 B: 牛妹的蛋糕 

问题 C: 尼科彻斯定理 

 问题 D: 单源最短路径问题

 问题 E: ABC + DEF = GHI

 问题 F: 油田问题

打印菱形 

题目描述

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

输入

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

输出

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

样例输入 Copy

2
3
4

样例输出 Copy

  * 
 * * 
* * * 
 * * 
  * 

   * 
  * * 
 * * * 
* * * * 
 * * * 
  * * 
   * 

    * 
   * * 
  * * * 
 * * * * 
* * * * * 
 * * * * 
  * * * 
   * * 
    * 

#include
using namespace std;


int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=1; i<=n+1; i++)
        {

            for(int j=1; j<=n+1-i; j++)
                cout<<" ";
            for(int k=1; k<=i; k++)
            {

                cout<<"* ";//每一个*后都要有空格，题目要求
            }
            cout<=1; i--)
        {
            for(int j=1; j<=n+1-i; j++)
                cout<<" ";
            for(int k=1; k<=i; k++)
            {

                cout<<"* ";
            }
            cout< 
 
问题 B: 牛妹的蛋糕  
题目描述
 
众所周知，牛妹非常喜欢吃蛋糕。
 
第一天牛妹吃掉蛋糕总数三分之一多一个，第二天又将剩下的蛋糕吃掉三分之一多一个，以后每天吃掉前一天剩下的三分之一多一个，到第n天准备吃的时候只剩下一个蛋糕。
 
牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？
 
输入
 
输入n，0 
输出
 
输出第一天蛋糕的数量。
 
样例输入 Copy
 
2
4
 
样例输出 Copy
 
3
10
 
#include

#define ll long long
const int N=10005;
using namespace std;
int a[N];


int main()
{

    int n;
    while(cin>>n){
           int  temp=1;
        for(int i=n-1;i>0;i--){
            temp=((temp+1)*3)/2;
        }
    cout< 
 
问题 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
 
 
 
 找规律的题，就是找到n*n-n后面开始的奇数就行了
 
 
#include
using namespace std;

int a[1005];

int main()
{
    int n;
    while(cin>>n){
        int cnt=n*n-n;
        int k=0,sum=0;

        for(int i=cnt;i<=n*n*n;i++){
            if(i%2==1){
                sum+=i;
                a[k++]=i;
                if(sum==n*n*n)break;
            }

        }
        for(int i=0;i 
 问题 D: 单源最短路径问题 
题目描述
 
编程实现Dijkstra算法，求一个有向加权图中，从源点出发到其他各个顶点的最短路径。
 
输入
 
第1行第1个值表示顶点个数，第2个值表示边个数；第2行开始为边（两个顶点，边的起点和终点）及权重。
 
输出
 
顶点0到每一个顶点的最短路径长度。
 
样例输入 Copy
 
5 7
0 1 10
0 3 30
0 4 100
1 2 50
2 4 10
3 2 20
3 4 60
 
样例输出 Copy
 
0 10 50 30 60
 
题解先看这里，这个比较简单题解
 
 
 问题 E: ABC + DEF = GHI 
题目描述
 
用1, 2, 3...9 这九个数字组成一个数学公式，满足：ABC + DEF = GHI，每个数字只能出现一次，编写程序输出所有的组合。
 
输入
 
无
 
输出
 
输出所有的 ABC + DEF = GHI，
 每行一条数据，格式为ABC+DEF=GHI
 输出结果按照ABC升序排列，如果ABC相同，则按照DEF升序排列。
 
 
 
就是一个简单的全排列问题，在这里调用了c++里面的stl库中的next_permutation（）函数，他就是一个全排列函数。如果你对stl库还不是太理解，可以看看我写的这篇文章
 
 
#include
using namespace std;

int a[]={1,2,3,4,5,6,7,8,9};
int main(){
do{
    if(a[0]*100+a[1]*10+a[2]+a[3]*100+a[4]*10+a[5]==a[6]*100+a[7]*10+a[8]){
        printf("%d%d%d+%d%d%d=%d%d%dn",a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]);
    }

}while(next_permutation(a,a+9));

return 0;
}
 
 
 
 问题 F: 油田问题 
 
  
  
题目描述
 
  
  
  
输入一个m行n列的字符矩阵，统计字符“@”组成多少个八连块。如果两个字符“@”所在的格子相邻（横、竖或者对角线方向），即属于同一个八连块。
 
  
 
 
  
  
输入
 
  
 
  多组输入
 输入行数m，以及列数n。
 然后输入*和@
 1<=n,m<=100
  
 
 
  
  
输出
 
  
 
  联通块个数
  
 
 
  
  
样例输入 Copy
 
  
 
   
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
 
  
 
  
  
 
 
  
  
样例输出 Copy
 
  
 
   
2
 
  
 
  
  
 
 
 
 这题就是深搜模板题吧，就是不断往四面八方搜索
 
 
#include
using namespace std;

int vis[105][105];
char c[105][105];
int m,n;
int sum;
void dfs(int i,int j)
{
    if(i>=m||j>=n||i<0||j<0)return;//注意边界问题
    if(c[i][j]=='*')return ;//如果不是@直接返回
    //以下就是深度搜索，往8个方向搜索判断是不是有@可以组成一个连通块，即
    //上、下、左、右、左上、右上、左下、右下。
    if(c[i+1][j]=='@'&&vis[i+1][j]==0)
    {
        vis[i+1][j]=1;//下
        dfs(i+1,j);
    }

    if(c[i-1][j]=='@'&&vis[i-1][j]==0)
    {
        vis[i-1][j]=1;//下
        dfs(i-1,j);
    }

    if(c[i][j-1]=='@'&&vis[i][j-1]==0)
    {
        vis[i][j-1]=1;//左
        dfs(i,j-1);
    }

    if(c[i][j+1]=='@'&&vis[i][j+1]==0)
    {
        vis[i][j+1]=1;//右
        dfs(i,j+1);
    }
    if(c[i-1][j-1]=='@'&&vis[i-1][j-1]==0)
    {
        vis[i-1][j-1]=1;//左上
        dfs(i-1,j-1);
    }

    if(c[i+1][j+1]=='@'&&vis[i+1][j+1]==0)
    {
        vis[i+1][j+1]=1;//右下
        dfs(i+1,j+1);
    }


    if(c[i+1][j-1]=='@'&&vis[i+1][j-1]==0)
    {
        vis[i+1][j-1]=1;//左下
        dfs(i+1,j-1);
    }

    if(c[i-1][j+1]=='@'&&vis[i-1][j+1]==0)
    {
        vis[i-1][j+1]=1;
        dfs(i-1,j+1);
    }
}
int main()
{
    while(cin>>m>>n)
    {
        int cnt=0;
        memset(vis,0,sizeof(vis));
        memset(c,0,sizeof(c));
        for(int i=0; i>c[i][j];
            }
        }
        for(int i=0; i