中國大學MOOC-陳越、何欽銘-資料結構-起步能力自測題筆記

中國大學MOOC-陳越、何欽銘-資料結構-起步能力自測題筆記

解題的方法有很多種，這些僅僅是我的解題方法，不是最優的，但是是我能最快想到的，

題集鏈接：https://pintia.cn/problem-sets/17/problems/type/7

自測1-列印沙漏

題意：給你n個字符，例如*，用這n個*字符組成這種型別的圖案，輸出能夠組成的最大的圖案和剩余的字符數量，

分析：只要計算出n個字符可以組成圖案的最大規模以及剩余的字符數量，再按照要求輸出該圖案即可，

思路：根據計算可得出圖案字符數量與規模的規律，分析每一行字符和空格與行數的關系，再把圖案上半部分和最中間那部分設計輸出，下半部分與上半部分對稱，只需倒過來輸出即可，

代碼：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,sum=1,m=0,temp=1;
    char x;
    scanf("%d",&n);
    getchar();
    scanf("%c",&x);
    if(n==1){
    	printf("%c\n",x);
    	printf("0\n");
	}else{
    while(n>sum){
        m+=1;
        temp=(temp+2);
        sum+=temp*2;
    }
    temp-=2;
    m-=1;
    for(int i=0;i<m;i++){
        for(int j=0;j<i;j++){
            printf(" ");
        }
        for(int j=0;j<temp-i*2;j++){
            printf("%c",x);
        }
        printf("\n");
    }
    for(int i=0;i<m;i++){
    	printf(" ");
	}
    printf("%c\n",x);
    for(int i=m-1;i>=0;i--){
        for(int j=0;j<i;j++){
            printf(" ");
        }
        for(int j=0;j<temp-i*2;j++){
            printf("%c",x);
        }
        printf("\n");
    }
    printf("%d\n",n-sum+(temp+2)*2);
}
    return 0;
}

自測2-素數對猜想

題意：給出一個數n，找出1-n內的素數對個數，素數對要滿足a,b都為素數，且a=b+2;

分析：找到1-n內的素數，在判斷那些素數對滿足a=b+2，

思路：回圈跑一遍3-n內的奇數，偶數不可能是素數，2也不能和哪個素數滿足a=b+2，判斷該數和該數加二的數是否都為素數，都為素數即是一個素數對，統計素數對數量即可，
判斷素數：如果該數x不能整除2到根號x中的任何一個數，那這個數即為素數，

代碼：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,temp,sum=0;
    scanf("%d",&n);
    for(int i=3;i<=n-2;i+=2){
        temp=0;
        for(int j=2;j<=sqrt(i);j++){
            if(i%j==0){
                temp=1;
                break;
            }
        }
        if(temp==0){
            //i+=2;
            for(int j=2;j<=sqrt(i+2);j++){
                if((i+2)%j==0){
                    temp=1;
                    break;
                }
            }
            if(temp==0){
                sum++;
//                printf("%d %d\n",i,i+2);
            }
        }
    }
    printf("%d\n",sum);
    return 0;
}

自測3-陣列元素回圈右移

題意：給出一組數和x，該組數每個位置上的數向右移x位，末位的數移到首位，輸出移位后的數列，

分析：每個數的實際位置改變了，但他們的相對位置不變，只要找出第一個數移位后的位置，根據相對位置就可以判斷出其他數的位置，

思路：位移位數取余陣列長度為首位的移位后的位置，（數列長度為n移位n后位置不變），把陣列中移位后的數移到最前（取余陣列長度即可），

代碼：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,n,x[110];
    scanf("%d%d",&m,&n);
    for(int i=0;i<m;i++){
        scanf("%d",x+i);
    }
    n=n%m;
    int temp=0;
    for(int i=m-n;i<m;i++){
        if(i!=m-n&&temp!=0){
            printf(" ");
        }
        printf("%d",x[i]);
        temp=1;
    }
    for(int i=0;i<m-n;i++){
    	if(temp!=0){
            printf(" ");
        }
        printf("%d",x[i]);
        temp=1;
    }
    return 0;
}

自測4-Have Fun with Numbers

題意：給出一個整數x，這個數乘2之后的數y，判斷組成x每個位上的數與y每個位上數是否相同，如x=132,y=264，這兩個不同，x由1，2，3組成，而y由2，4，6組成，

分析：給出的數很大，超出了數字型別的最大范圍，首先想到大數運算，用字串模擬數字運算，再記錄x與y每個位上的數記錄下來，最后對比即可，

思路：用字串陣列模擬整數，用一個陣列儲存0-9在x每個位上出現的次數，對每個位上的數乘二逢10進位表示y，用一個陣列儲存0-9在y每個位上出現的次數，最后比較兩個陣列是否相同，

代碼：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    char x[31],y[31];
    int a[20],b[20],num1[31],num2[31],temp=0;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    scanf("%s",x);
    int len1=strlen(x),len2;
    for(int i=0;i<len1;i++){
        a[x[i]-'0']++;
        num1[i]=x[i]-'0';
    }
    for(int i=len1-1;i>=0;i--){
        int p=(num1[i]*2+temp);
        num2[len1-1-i]=p%10;
        b[p%10]++;
        temp=p/10;
    }
    len2=len1;
    if(temp!=0){
        num2[len1]=temp;
        len2+=1;
        b[temp]++;
    }
    temp=0;
    for(int i=0;i<10;i++){
        if(a[i]!=b[i]){
            temp=1;
            break;
        }
    }
    if(temp==0){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
    for(int i=len2-1;i>=0;i--){
        printf("%d",num2[i]);
    }
    return 0;
}

自測五-Shuffling Machine

題意：模擬洗牌，給出牌的初始序列和洗牌規則，要求按照這個規則洗牌k次，輸出牌經過k次洗牌后的序列，
洗牌規則：給出一組數列，數列長度和牌的長度一樣，第i個數a[i]表示第i張牌洗到第a[i]個位置上，

分析：只要按照規則洗牌，記錄每次洗牌后的牌的順序，最后再輸出牌的順序即可，

思路：用兩個陣列，輪番記錄每次洗牌前后的牌的順序，洗牌k次后數次洗牌后的牌序列即可，

代碼：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string x[60]={"S1","S2","S3","S4","S5","S6","S7","S8","S9","S10","S11","S12","S13"
        ,"H1","H2","H3","H4","H5","H6","H7","H8","H9","H10","H11","H12","H13"
        ,"C1","C2","C3","C4","C5","C6","C7","C8","C9","C10","C11","C12","C13"
        ,"D1","D2","D3","D4","D5","D6","D7","D8","D9","D10","D11","D12","D13"
        ,"J1","J2"},y[60],z[60];
    int n,ord[60];
    scanf("%d",&n);
    for(int i=0;i<54;i++){
        scanf("%d",ord+i);
//        y[ord[i]]=x[i];
    }
    while(1){
        for(int i=0;i<54;i++){
            y[ord[i]-1]=x[i];
        }
        n-=1;
        if(n==0){
            for(int i=0;i<54;i++){
                if(i!=0){
                    cout<<" ";
                }
                cout<<y[i];
            }
            break;
        }
        for(int i=0;i<54;i++){
            x[ord[i]-1]=y[i];
        }
        n-=1;
        if(n==0){
            for(int i=0;i<54;i++){
                if(i!=0){
                    cout<<" ";
                }
                cout<<x[i];
            }
            break;
        }
    }
    return 0;
}

親身下河知深淺，親口嘗梨知酸甜，