特殊四位数

问题描述

数学一直是明明很喜欢的一门学科，不但上课认真听讲，而且还自己钻研。有一次，老师在课上讲了一种特殊的四位整数，这种整数有两个特性：

第一，它是某一个自然数的平方；

第二，它的千位数字与十位数字之和等于百位数字与个位数字之积。

然后老师就举了一个例子：1156，1156是34的平方，且1156的千位数字1加上十位数字5等于百位数字1乘以个数数字6，即1+5=1*6。

然后老师告诉同学，这是最小的一个符合以上两个特性的四位整数，接着老师就留下了作业，要让同学们回家后尽量多的找出符合这两个特性的特殊四位数。明明回家后，就开始找了起来，1157、1158、1159、……、3136，直到到了3136（3136=56*56，3+3=1*6），明明才找到了第二个这样的特殊四位数。明明觉得这样找下去不是办法，后面还有好几千个数字要一个一个试下来，这样一定无法在睡觉前完成。于是明明就求助于你，帮他写一个程序，从小到大求出所有的这样的特殊四位数，然后当明明想要第几个这样的特殊四位数时，你就能够很快的告诉他。 如果把上述所有的特殊四位数按从小到大的顺序排列后记为S1，S2，…，Sn，…，即排在第1个位置上的特殊四位数记为S1，排在第2个位置上的特殊四位数记为S2，…，排在第n个位置上的特殊四位数记为Sn，那么明明的问题可以归结为：假如一个特殊四位数排在第n个位置上，那么这个特殊四位数Sn等于多少呢？

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据仅占一行，每行仅有一个正整数n（n不大于特殊四位数的个数），表示要求第n个特殊四位数Sn。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将这一组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一个正整数，表示与输入数据n相对应的那个特殊四位数Sn，每组运算结果单独形成一行数据，其行首和行尾都没有任何空格，每组运算结果与其后一组运算结果之间没有任何空行，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行。 注：通常，显示屏为标准输出设备。

解题思路：

循环遍历i*i可以获得的四位数字，算出个位十位百位千位，如果满足题意count加一，找到第n个特殊四位数Sn则输出

初始代码：

#include <stdio.h>

int main(){
    int n;
    while (scanf("%d",&n) != EOF){
        int count=0;
        for(int i=30;i<100;i++){
            int x=i*i;
            if(x>999 && x<10000){
                int a=x%10;
                int b=x/10%10;
                int c=x/100%10;
                int d=x/1000%10;
                if(a*c == b+d){
                    count++;
                }
                if(count==n){
                    printf("%d\n",x);
                    break;
                }
                }
            }
            
        }
    return 0;
}

AC代码：同上

错误反思：

最大值

问题描述

为了培养明明对数学的热爱，明明的爸爸经常想出一些简单有趣且富有数学思想的游戏给明明玩。有一次，明明的爸爸在纸上写了N个数字，有正整数、负整数和0。明明的爸爸给明明一个范围，他可以选大于等于L1个且小于等于L2个的数字（L1≤L2），且这些数字必须是连续的。但是要求明明选出的数的和最大，这样说明明可能不太明白，于是明明爸爸就举了一个简单的例子。 例如有5个数字为“1”、“2”、“3”、“4”、“5”，明明可以选择大于等于1个且小于等于2个的数字，也就是说明明可以选择1个数字，或者连续的2个数字。通过观察数字串，最后我们会选2个数字，4和5，他们的和最大，为9。 明明明白爸爸的意思后，就开始玩起游戏来。但是他发现，这个游戏看似简单，其实还是有相当的难度，因为数字越多，选择数字个数范围越大，则题目越难，到后面明明有些不想玩了。于是明明就求助于你，请你帮他写一个程序，来求出和的最大值。 明明的问题可以归结为：有N个数字，从中选择出连续的M(L1≤M≤L2)个数，求出它们之和的最大值。

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据有两行，每组测试数据的第一行有三个整数N(0<N≤20)、L1、L2(0<L1≤L2≤N)，N表示数字串中有多少个整数，L1、L2表示可选数字个数的范围，每组测试数据的第二行有N个整数，整数大小的绝对值都小于等于100，整数之间用一个空格隔开。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将每组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一个整数，即所求的最大值。每组运算结果单独形成一行数据，其行首和行尾都没有任何空格，每组运算结果与其后一组运算结果之间没有任何空行，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行。 注：通常，显示屏为标准输出设备。

解题思路：

把输入数据存到一个数组中，分别算出从L1--L2，满足要求max的最大值

初始代码：

//0.8/1五测试用例过3
#include <stdio.h>

int main(){
    int N,L1,L2;
    while(scanf("%d %d %d",&N,&L1,&L2) != EOF){
        int a[21];
        //输入数字并存到数组中
        for(int i=0;i<N;i++){
            int n;
            if (i==0) {
                scanf("%d",&n);
            }else scanf(" %d",&n);
            a[i]=n;
        }
        
        int max=0,sum=0;
        //定范围
        for(int i=L1;i<=L2;i++){
        //定开头
            for(int j=0;j<N-i+1;j++){
                sum=0;
        //定范围内和
                for(int k=0;k<i;k++){
                    sum+=a[j+k];
                }
                if(sum>max){
                    max=sum;
                }
            }
        }
        printf("%d\n",max); 
        }
    return 0;
}

二次调整

max初始值设为0，当最大值为负时输出也会变成0

修改   int max=0;    为   int max=-999;

AC代码：

#include <stdio.h>

int main(){
    int N,L1,L2;
    while(scanf("%d %d %d",&N,&L1,&L2) != EOF){
        int a[21];
        //输入数字并存到数组中
        for(int i=0;i<N;i++){
            int n;
            if (i==0) {
                scanf("%d",&n);
            }else scanf(" %d",&n);
            a[i]=n;
        }
        
        int max=-999,sum=0;
        for(int i=L1;i<=L2;i++){
            for(int j=0;j<N-i+1;j++){
                sum=0;
                for(int k=0;k<i;k++){
                    sum+=a[j+k];
                }
                if(sum>max){
                    max=sum;
                }
            }
        }
        printf("%d\n",max); 
        }
    return 0;
}

错误反思：

数列1

问题描述

思维的严密性是相当重要的，尤其是在程序设计中，一个小小的错误，就可能导致无法想象的后果。明明的爸爸是一名富有经验的程序设计专家，深知思维严密的重要性。于是在明明很小的时候，就通过游戏的方式训练明明的思维严密性。今天，明明的爸爸和明明做了一个数列的游戏。

这个游戏很简单，就是有一数列，现在需要在数列中选出一个或者连续若干个数，要求这些数的和能被11整除。明明的爸爸想锻炼明明思维的严密性，因此要求明明尽可能多的找出符合条件的数列来，最好一个也不要漏掉。 例如有一数列为“11 22 33”，其中11可以被11整除，22可以被11整除，33可以被11整除，11+22=33能被11整除，22+33=55能被11整除，11+22+33=66能被11整除。所以以上一数列能被11整除的情况一共有六种。（注：虽然11+33也能被11整除，但是11和33在数列中没有连续出现，因此不算一种合理的情况。） 明明对这个游戏很感兴趣，高兴地玩了起来。由于粗心，明明总是无法一次就把所有的情况都找出来，这使得他爸爸不是很满意。于是明明爸爸决定先降低游戏的难度，事先告诉明明某一数列总共有多少种符合条件的选择数的方法，然后再让明明去选。明明的爸爸请你帮一个忙，他不想自己找出所有的情况，因此请你写一个程序，用程序来找出一共有多少种符合选数的情况，并把结果告诉他。 明明爸爸的问题可以归结为：给你一个数列，从中选出1个或连续若干个数，要求这些数的和能被11整除，问这样的选数方法一共有多少种。

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据有两行，每组测试数据的第一行有一个整数n(0<n≤50)，表示数字串中有多少个整数，每组测试数据的第二行有n个整数，整数大于等于0且小于等于100，整数之间用一个空格隔开。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将每组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一个整数，即表示一共有多少种选数方法。每组运算结果单独形成一行数据，其行首和行尾都没有任何空格，每组运算结果与其后一组运算结果之间没有任何空行，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行。 注：通常，显示屏为标准输出设备。

解题思路：

与上题相似，三循环求每一次的和，count统计满足要求的次数

初始代码：

#include <stdio.h>

int main(){
    int n;
    while (scanf("%d",&n) != EOF){
        int a;
        int b[51];
        for(int i=0;i<n;i++){
            if (i==0) {
                scanf("%d",&a);
            }else scanf(" %d",&a);
            b[i]=a;
        }
        int count=0;
        //每次选几个
        for(int i=1;i<=n;i++){
            //每次从哪开头
            for(int j=0;j<n-i+1;j++){
                int sum=0;
                for(int k=0;k<i;k++){
                    sum+=b[j+k];
                }
                if(sum%11==0) count++;
            }
        }
        printf("%d\n",count);
    }
    return 0;
}

AC代码：同上

错误反思：

修理牛棚（★）

问题描述

在一个暴风雨的夜晚，农民约翰的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假，所以牛棚（牛棚的总数S:1<= S<=200）没有住满。 剩下的牛一个紧挨着另一个被排成一行安置在有屋顶的牛棚来过夜。 所以有些牛棚里有牛，有些没有。

所有的牛棚有相同的宽度，且宽度设为1。 因为有些门遗失，农民约翰需要架起新的木板作为门。 他的新木材供应者将会供应他任何他想要的长度,但是供应者只能提供有限数目的木板。 农民约翰想将他购买的木板总长度减到最少。

计算拦住所有有牛的牛棚所需木板的最小总长度。

输出所需木板的最小总长度作为的答案。

说明：拦住一个牛棚需要的木板长度为1，拦住相邻的三个牛棚则需要木板长度为3。

比如有牛的牛棚编号为：

3 5 8 10 11

并且只能使用两块木板，

则第一块木板从3到5，长度为3，

第二块木板从8到11，长度为4，

因此，需要木板的总长度为7。

输入说明

第 1 行: M 和 C(用空格分开)

第 2 到 C+1行: 每行包含一个整数，表示牛所占的牛棚的编号。

其中：

可能买到的木板最大的数目：M(1<= M<=50);

需要安置的牛的数目C(1<= C <=S)

安置后牛所在的牛棚的编号stall_number(1<= stall_number <= S)。

输出说明

单独的一行包含一个整数表示所需木板的最小总长度

解题思路：

输入到一个数组中，排序，没思路了

二编：先用一块木板覆盖住所有牛棚，每增加一块木板，就可以将间隔最大的隔开

• 如果用一块木板覆盖所有牛，长度就是 max(stall) - min(stall) + 1。

• 但如果允许用多块木板，我们可以从间隔最大的地方断开，这样能减少不必要的覆盖（覆盖了中间的空牛棚）。

初始代码（AI）：

#include <stdio.h>
#include <stdlib.h>

// 比较函数，用于排序
int cmp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

int main() {
    int M, C;
    scanf("%d %d", &M, &C);
    
    int stalls[201];  // 最多200个牛棚
    for (int i = 0; i < C; i++) {
        scanf("%d", &stalls[i]);
    }
    
    // 1. 排序牛棚编号
    qsort(stalls, C, sizeof(int), cmp);
    
    // 2. 计算初始总长度（用一块木板覆盖所有）
    int total_length = stalls[C-1] - stalls[0] + 1;
    
    // 3. 计算所有间隔
    int gaps[201];
    int gap_count = 0;
    for (int i = 0; i < C-1; i++) {
        gaps[gap_count++] = stalls[i+1] - stalls[i] - 1;
    }
    
    // 4. 对间隔从大到小排序
    // 使用冒泡排序（或qsort，但需要降序）
    for (int i = 0; i < gap_count-1; i++) {
        for (int j = 0; j < gap_count-1-i; j++) {
            if (gaps[j] < gaps[j+1]) {
                int temp = gaps[j];
                gaps[j] = gaps[j+1];
                gaps[j+1] = temp;
            }
        }
    }
    
    // 5. 减去最大的 M-1 个间隔
    // 最多只能减 M-1 个间隔（因为 M 块木板可以有 M-1 个断点）
    int boards_to_use = M;
    if (boards_to_use > C) boards_to_use = C;  // 木板数不能超过牛的数量
    
    // 每多一块木板，就能减去一个间隔
    for (int i = 0; i < boards_to_use - 1 && i < gap_count; i++) {
        total_length -= gaps[i];
    }
    
    printf("%d\n", total_length);
    return 0;
}

AC代码：同上

错误反思：

按要求输出序列

问题描述

明明的爸爸是一位著名的数学家。他在明明很小的时候就发现明明有过人的数学天赋，因此有意培养他对数学的兴趣。一次，明明的爸爸为了培养明明对数字的敏感，和明明玩起了一个数字游戏，这个游戏的名称叫“按要求输出序列”。在游戏中，明明的爸爸给了明明一串数字，要求明明首先把这串数字中重复出现的数字删除到仅剩一个，即相同的数字只保留一个，然后将这串数字从小到大进行排序。明明很快就理解了游戏的规则，开始玩起来。明明的爸爸首先给了明明三个数字：3、2、1；明明很快就回答说：“1、2、3”。明明的爸爸惊讶于明明的反应能力，开始加大游戏的难度，给出了由6个数字组成的数字串：2、1、4、3、5、2；明明眼珠子一转，脱口而出：“1、2、3、4、5”（由于“2”出现了两次，因此要删除一个，然后再排序输出。）。明明的爸爸意识到简单的数字串难不住明明，于是决定给出很长的一串数字串来考明明。但与此同时，明明爸爸面对这很长的数字串也无法一时计算出最后的结果，于是就求助于你，让你帮他写一个程序，用来计算出数字串最后的结果。

明明的爸爸的问题可以归结为：给你一个数字串，里面有n个数字，首先对数字串中的数字进行处理，删除重复出现的数字（重复出现的数字只保留一个），然后对数字串从小到大进行排序，最后输出排序后的字符串。

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据占两行：

第一行是一个正整数n（1≤n≤200），表示数字串中有n个数字，

第二行是n个数字，n个数字都大于等于0且小于等于10^9，每两个数字用一个空格隔开。

每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将这一组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一个排序后的数字串，数字串中的数字用一个空格隔开。每组运算结果单独形成一行数据，其行首和行尾都没有任何空格，每组运算结果与其后一组运算结果之间没有任何空行，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行。 注：通常，显示屏为标准输出设备。

解题思路：

新建一个数组，遍历原数组，每次找最小项，找之前先判断这个值是否已经存到新数组中

初始代码：

//0.8/1 只通过一个测试用例
#include <stdio.h>

int main(){
    int n;
    while (scanf("%d",&n) != EOF){
        int a;
        int b[201];
        for(int i=0;i<n;i++){
            if (i==0) {
                scanf("%d",&a);
            }else scanf(" %d",&a);
            b[i]=a;
        }
        int c[201]={0};
        int current=b[0];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(b[j]<current){
                    current=b[j];
                }
            }
            c[i]=current;
        }
        for(int i=0;i<n;i++){
            if(c[i] != 0){
                if(i==0){
                    printf("%d",c[i]);
                }else printf(" %d",c[i]);
            }
        }
        printf("\n");
    }
    return 0;
}

二次调整

//0.95/1  一个测试用例不通过

选择最小值出现错误
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(b[j]<current){
                    current=b[j];   

//当第一个最小值选出来后，后面所有的b[j]都大于current，无法进入循环
                }
            }
            c[i]=current;
        }

修改为
        for(int i=0;i<n;i++){
            int current=1000000001;
            for(int j=0;j<n;j++){
                int found=0;
                for(int k=0; k<i; k++){
                    if(c[k] == b[j]){
                    found = 1;
                    break;
                    }
                }
                
                if(b[j]<current && found==0){
                    current=b[j];
                }
            }
            if(current != 1000000001){
            c[i] = current;
            }

三次调整

有可能含值为0的数，代码逻辑直接跳过了

        for(int i=0;i<n;i++){
            if(c[i] != 0){
                if(i==0){
                    printf("%d",c[i]);
                }else printf(" %d",c[i]);
            }
        }

修改为

           int count =0;

               ......

            if(current != 1000000001){
                c[i] = current;
                count++;
            }

                ......

         for(int i=0;i<count;i++){
                if(i==0){
                    printf("%d",c[i]);
                }else printf(" %d",c[i]);
        }

//添加一个统计有效项的count位

AC代码：

#include <stdio.h>

int main(){
    int n;
    while (scanf("%d",&n) != EOF){
        int a;
        int b[201];
        for(int i=0;i<n;i++){
            if (i==0) {
                scanf("%d",&a);
            }else scanf(" %d",&a);
            b[i]=a;
        }
        int c[201]={0};
        int count=0;
        for(int i=0;i<n;i++){
            int current=1000000001;
            for(int j=0;j<n;j++){
                int found=0;
                for(int k=0; k<i; k++){
                    if(c[k] == b[j]){
                    found = 1;
                    break;
                    }
                }
                
                if(b[j]<current && found==0){
                    current=b[j];
                }
            }
            if(current != 1000000001){
                c[i] = current;
                count++;
            }
        }
        for(int i=0;i<count;i++){
                if(i==0){
                    printf("%d",c[i]);
                }else printf(" %d",c[i]);
        }
        printf("\n");
    }
    return 0;
}

错误反思：

转载自CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/foolgod_0/article/details/157773941