程序设计基础作业03-数组练习

GitHub

738NGX/Programming-Basics-Homework-03

【实验准备】

实验教材：《C++程序设计实验指导》（第二版），孟桂蛾编，上海交大出版社，2019

IDE: Microsoft Visual Studio Code September 2022 (version 1.71.2)

编译器：MingW-W64-builds 10.0.0 & GCC 12.1.0

操作系统：Windows 11 家庭中文版22H2 22623.870 Beta Preview（64-bit）

【实验题目】

1.打印杨辉三角形

问题描述：由杨辉三角形可以看出每行的数存在如下规律：每行数据的个数和行序相同；每行的第一个数和最后一个数都是 1；中间的数为上一行中前一列的数和后一列的数之和。
请编写程序，用户输入要打印的杨辉三角形的总行数 n，程序打印出总行数为 n 的杨辉三角形。
提示：可以应用循环语句和一个二维数组，并控制输出间距来打印杨辉三角形。

使用一个初始值均为0动态二维数组，其大小由n决定；

为三角形最外层赋值1搭建框架，随后按照公式计算出整个三角形；

最终输出时遇0则不输出，否则输出对应数值；输出间隔通过switch语句根据n的值动态调整。

#include<iostream>
using namespace std;

int main(){
    int input;                                    //输入的预期行数
    int **pascalTriangle;                        //杨辉三角:动态二维数组
    int i,j,k;                                    //计数器
    cout<<"请输入要打印的杨辉三角形的总行数n:";
    cin>>input;
    int line=input;                                //实际行数
    int column=2*input-1;                        //实际列数
    pascalTriangle=new int *[line];                //申请每一行首地址指针

    //为每一行申请空间
    for(i=0;i<line;i++){
        pascalTriangle[i]=new int[column];
    }

    //为杨辉三角所有元素赋初值0
    for(i=0;i<line;i++){
        for(j=0;j<column;j++){
            pascalTriangle[i][j]=0;
        }
    }

    //建立三角型框架:最外层赋值为1
    pascalTriangle[0][input-1]=1;
    j=1;
    for(i=1;i<line;i++){
        pascalTriangle[i][input-1+j]=1;
        pascalTriangle[i][input-1-j]=1;
        j++;
    }

    //计算三角形元素:中间的数为上一行中前一列的数和后一列的数之和
    for(i=1;i<line;i++){
        for(j=1;j<column-1;j++){
            pascalTriangle[i][j]=pascalTriangle[i-1][j-1]+pascalTriangle[i-1][j+1];
        }
    }

    //最终输出:为0不输出，不为0时输出对应值;每一位数字随n的变化调整占位
    switch(line/12){
        case 0:
            for(i=0;i<line;i++){
                for(j=1;j<line-i;j++){
                    printf("  ");
                }
                for(j=0;j<column;j++){
                    if(pascalTriangle[i][j]==0){
                        continue;
                    }
                    else{
                        printf("%-4d",pascalTriangle[i][j]);
                    }            
                }
                cout<<endl;        //完整输出一行后换行
            }
            break;
        case 1:
            for(i=0;i<line;i++){
                for(j=1;j<line-i;j++){
                    printf("    ");
                }
                for(j=0;j<column;j++){
                    if(pascalTriangle[i][j]==0){
                        continue;
                    }
                    else{
                        printf("%-8d",pascalTriangle[i][j]);
                    }            
                }
            cout<<endl;        //完整输出一行后换行
            }
            break;
        default:
            for(i=0;i<line;i++){
                for(j=1;j<line-i;j++){
                    printf("      ");
                }
                for(j=0;j<column;j++){
                    if(pascalTriangle[i][j]==0){
                        continue;
                    }
                    else{
                        printf("%-12d",pascalTriangle[i][j]);
                    }            
                }
            cout<<endl;        //完整输出一行后换行
            }
            break;
    }
    return 0;
}

2.字符串排序

问题描述：输入 5 个不相同的字符串，将它们按照字母序由小到大顺序排列并输出。可以考虑字符数组或string 类型数组保存输入的字符串，然后采用冒泡或选择排序 方法实现排序并输出。

程序运行示例：

Please input strings: 
China India Korea Japan Canda 
Sorted Strings: 
Canda China India Japan Korea

字符串使用string类储存，排序使用冒泡排序

#include<iostream>
#include<vector>
using namespace std;

const int len=5;                            //字符串个数

int main(){
    int i,j;                                //计数器
    bool flag;                                //记录一次起泡中是否发生过交换
    vector<string> str;                        //字符串容器
    string input;                            //用户输入的字符串
    cout<<"Please input strings:"<<endl;

    //用户输入
    for(i=1;i<=len;i++){
        cin>>input;
        str.push_back(input);
    }
    cout<<endl;

    //冒泡排序
    for(i=1;i<len;i++){
         flag=false;                            //记录重置
        for(j=0;j<len-i;j++){
            if(str[j+1]<str[j]){
                str[j].swap(str[j+1]);        //字符串交换
                flag=true;                    //标记
            }
        }
        if(!flag){
            break;                            //没有发生交换,终止排序
        }
    }

    //最终输出
    cout<<"Sorted Strings:"<<endl;
    for(i=0;i<len;i++){
        cout<<str[i]<<endl;
    }
    return 0;
}

3.判断黑色星期五

问题描述：黑色星期五是指某天既是 13 号又是星期五。13 号在星期五的情况比在其他日子的少吗？为了回答这个问题，编写一个程序，计算每个月的 13 号分别落在周一到周日的次数。给出一个正整数 n （n 不大于400），要求计算从 1900 年 1 月 1 日至 1900+n-1 年 12 月 31 日中 13 号落在周一到周日的次数.（已知 1900 年 1 月 1 日是星期一）

程序运行示例：

20
34 33 35 35 34 36 33

用到函数：int year2startDay(int year) 输入一个1900年及以后的年份，计算其1月1日是星期几；vector<int> dateNum(int date,bool leapYear)

输入日期，将每月的该日期转换为其在一年中的第几天；

(dateNum(tgDate,ifLeapYear(year))[month-1]%7+year2startDay(year)-1)%7通过此公式计算得到星期结果并计数

#include<iostream>
#include<vector>
using namespace std;

vector<int> dateNum(int date,bool leapYear);
bool ifLeapYear(int year);
int year2startDay(int year);

const int tgDate=13;        //需要求的目标日期

int main(){
    int day[7]={0};         //day[n]即星期n
    int n;                    //输入年数
    cout<<"请输入n:";
    cin>>n;

    //计数阶段
    for(int year=1900;year<1900+n;year++){
        for(int month=1;month<=12;month++){
            switch((dateNum(tgDate,ifLeapYear(year))[month-1]%7+year2startDay(year)-1)%7){
                //计算year年month月tgDate日是星期几，表达式结果范围在-1~6之间，对应结果如下:
                case -1: day[6]++; break;  case 0: day[0]++; break;
                case 1: day[1]++; break;   case 2: day[2]++; break;
                case 3: day[3]++; break;   case 4: day[4]++; break;
                case 5: day[5]++; break;   case 6: day[6]++; break;
            }
        }
    }

    //最终输出
    cout<<"MON\tTUE\tWED\tTHU\tFRI\tSAT\tSUN"<<endl;
    for(int i=1;i<=6;i++){
        cout<<day[i]<<"\t";
    }
    cout<<day[0]<<endl;
    return 0;
}

/**
 * @brief 输入日期，将每月的该日期转换为其在一年中的第几天
 * 
 * @param date 输入日期
 * @param leapYear 是否为闰年
 * @return 每月date日所对应的在一年中的第几天，一个长度为12的整型数容器
 */
vector<int> dateNum(int date,bool leapYear){
    vector<int> target;
    int n=date;    
    target.push_back(n);
    for(int i=1;i<12;i++){
        switch(i){
            case 1: n+=31; break; case 11: n+=30; break;
            case 2:
                if(!leapYear)
                    n+=28;
                else
                    n+=29;
                break;
            case 3: n+=31; break; case 4: n+=30; break;
            case 5: n+=31; break; case 6: n+=30; break;
            case 7: n+=31; break; case 8: n+=31; break;
            case 9: n+=30; break; case 10: n+=31; break;
        }
        target.push_back(n);
    }
    return(target);
}

/**
 * @brief 判断某个年份是否为闰年
 * 
 * @param year 输入年份
 * @return true 是闰年
 * @return false 不是闰年
 */
bool ifLeapYear(int year){
    return((year%4==0&&year%100!=0)||(year%400==0));
}

/**
 * @brief 输入一个1900年及以后的年份，计算其1月1日是星期几
 * 
 * @param year 输入年份
 * @return year年的1月1日是星期几
 */
int year2startDay(int year){
    int startDay=1;                    //year年的1月1日是星期几
    for(int i=1901;i<=year;i++){
        if(ifLeapYear(i-1))
            startDay+=2;
        else
            startDay++;
        if(startDay>=7)
            startDay-=7;
    }
    return(startDay);
}

4. 寻找整数矩阵元素的最大值

问题描述：有一个 3×4 的整数矩阵，使用二维整数数组表示，示例如下：
int a[3][4]={{30,25,23,56},{12,2,6,46},{-12,-34,16,28}};
要求编程序输出其中值最大的那个元素的值，以及其所在的行号和列号。

算法如下：先把 a[0][0]的值赋给变量 max，然后通过两层循环、一次遍历整个数组的元素，让每个被访问到元素与 max 进行比较，如果其值大于 max，则将该值保存在 max 中，并记录下该元素的行和列的值，重复这个过程，直到最后一个元素为止。

#include<iostream>
using namespace std;

int main()
{
    int a[3][4]={{30,25,23,56},{12,2,6,46},{-12,-34,16,28}};    //定义数组
    int max=a[0][0];                                            //max大小初始化
    int maxX,maxY;                                                //max坐标初始化
    
    //遍历循环查找max并且记录值和坐标
    for(int i=0;i<3;i++){
        for(int j=0;j<4;j++){
            if(a[i][j]>max){
                max=a[i][j];
                maxX=i;
                maxY=j;
            }
        }
    }

    //最终输出
    printf("max=%d,row=%d,column=%d\n",max,maxX,maxY);
    return 0;
}

5. 寻找整数矩阵元素的多个最大值及其位置

问题描述：上题（第4题）算法在处理有多个最大值的数组时，只能输出遍历时访问的第一个最大值及其位置，例如对于如下数组：
int a[3][4]={{27,12,23,56},{37,2,56,46},{-12,-34,56,8}};
输出如下：
max = 56，row = 0，column = 3
请修改第 4 题中的算法，编程要求仍然通过两层循环（一次遍历所有元素），找出所有最大值元素及其它们的位置。最后输出它们。仍以上面数组为例，输出如下：
max = 56，row = 0，column = 3
max = 56，row = 1，column = 2
max = 56，row = 2，column = 2

增加了两个整型数容器分别依次记录最大值的横纵坐标；一旦最大值更新则清空容器重新记录

#include<iostream>
#include<vector>
using namespace std;

int main()
{
    int a[3][4]={{27,12,23,56},{37,2,56,46},{-12,-34,56,8}};    //定义数组
    int max=a[0][0];                                            //max定义及大小初始化
    vector<int> maxX,maxY;                                        //max坐标容器定义及初始化
    maxX.push_back(0);
    maxY.push_back(0);
    
    //遍历循环查找max并且记录值和坐标
    for(int i=0;i<3;i++){
        for(int j=0;j<4;j++){
            if(a[i][j]>=max){
                //最大值发生更新，清空容器重新计数
                if(a[i][j]>max){
                    maxX.erase(maxX.begin(),maxX.end());
                    maxY.erase(maxY.begin(),maxY.end());
                    max=a[i][j];
                }
                maxX.push_back(i);
                maxY.push_back(j);
            }
        }
    }

    //最终输出
    for(int i=0;i<maxX.size();i++)
        printf("max=%d,row=%d,column=%d\n",max,maxX[i],maxY[i]);
    return 0;
}

6. 附加题：报数离队问题

问题描述：有 20 个人围成一个圆圈玩报数游戏：每人背后依次贴上一个编号(编号从 0 到 19)，从第 0 号的人开始从 1 报数，第 1 号的人报数 2，…，凡报到 3 的倍数的人离开圈子，后面的人继续往下报数，直到最后只剩下一个人为止。请程序模拟上面的游戏过程，按顺序将依次离开圈子的人的编号打印出来。
提示：可以考虑设计一个数组和一个整型变量来帮助程序的设计。

设计一个数组用来保存是否离开圈子的状态。
bool isInGroup[20];
// isInGroup[i] = true 表示编号为 i 的人在圈子里，否则表示他/她离开圈子；由于开始时，所有 20 人都在圈子里，所以 isInGroup[20]需要如下初始化：
for (int i=0;i<20;i++) isInGroup[i] = true;
定义一个变量 personNumberInGroup 来表示当前还有多少人在圈子里，初值是 20，所以可以定义如下：
int personNumberInGroup = 20

#include<iostream>
using namespace std;

bool isInGroup[20];

int main(){
    bool isInGroup[20];                                //是否还在圈内
    for (int i=0;i<20;i++) 
        isInGroup[i]=true;                    
    int personNumberInGroup=20;                        //当前圈内人数
    int flag=0;                                        //报数统计标志
    while(personNumberInGroup>1){                    //不到最后一人不停止
        for(int i=0;i<20;i++){                      //开始一轮报数
            if(isInGroup[i])                        //还在圈内，报数
                flag++;
            if(flag==3){                            //达到3的倍数，离开圈子，flag归零
                isInGroup[i]=false;
                personNumberInGroup--;
                flag=0;
                printf("Player %d quited.\n",i);    //打印出局者
            }
        }
    }
    for (int i=0;i<20;i++) 
        if(isInGroup[i])
            printf("Player %d winned.\n",i);        //打印幸存者
    return 0;
}