PTA 编程题(C语言)-- 简化的插入排序

这篇具有很好参考价值的文章主要介绍了PTA 编程题(C语言)-- 简化的插入排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目标题:简化的插入排序       题目作者:C课程组 浙江大学

本题要求编写程序,将一个给定的整数插到原本有序的整数序列中,使结果序列仍然有序。

输入格式:

输入在第一行先给出非负整数N(<10);第二行给出N个从小到大排好顺序的整数;第三行给出一个整数X。

输出格式:

在一行内输出将X插入后仍然从小到大有序的整数序列,每个数字后面有一个空格。

输入样例:

5
1 2 4 5 7
3

输出样例:

1 2 3 4 5 7 

思路1:(1)输入整数到变量N;声明一个数组A[N](有些古早的编译器不允许在程序中用变量做为数组的长度来声明数组,这里也可同一声明为A[10]),把第二行的N个数一次读入到数组A中;输入要插入的整数到变量X。

(2)遍历数组的每个元素A[i],如果X < A[i],就先输出X,再输出A[i];否则就直接输出A[i]。这里注意,如果执行某一次循环体时,已经将X输出了,那么后面的循环体就不用再输出X了。这里有一个小技巧,用flag=1标记X尚未输出,flag=0标记X已经输出。

代码1:

#include <stdio.h>
int main () {
    int N,X,i,flag=1;
    int A[10];
    scanf("%d", &N);
    for (i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }
    scanf("%d", &X);
    for (i = 0; i < N; i++) {
        if (flag && X < A[i]) {
            printf("%d ", X);
            flag = 0;
        }
        printf("%d ", A[i]);
    }
    if (flag) printf("%d ", X);
    return 0;
}

这里说一下代码1的优缺点。(1)不改变数组A的结构,只是在按顺序输出数组A的元素的过程中,在适当的时机插入X的输出。(2)每次执行循环体都要判断一下flag的值。

思路2:(1)输入整数到变量N;声明一个数组A[N](有些古早的编译器不允许在程序中用变量做为数组的长度来声明数组,这里也可同一声明为A[10]),把第二行的N个数一次读入到数组A中;输入要插入的整数到变量X。给变量flag赋值为N,这里的N用来标记要插入的位置。

(2)遍历数组的每个元素A[i],如果 A[i] < x,就输出A[i];否则标记flag=i,并跳出循环。接着输出一个X。再接着从A[flag]开始输出剩余的数组A中的元素。

代码2:

#include <stdio.h>
int main () {
    int N,X,i,flag;
    int A[10];
    scanf("%d", &N);
    flag = N;
    for (i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }
    scanf("%d", &X);
    for (i = 0; i < N; i++) {
        if (A[i] < X) printf("%d ", A[i]);
        else {
            flag = i;
            break;
        }
    }
    printf("%d ", X);
    for (i = flag; i < N; i++) printf("%d ", A[i]);
    return 0;
}

代码2相较于代码1的优点是减少了if内条件判断的次数。

代码1和代码2,都没有改变原数组的结构。这对新手比较友好。但是有的时候我们需要通过改变数组的结构来完成一定的功能。下面就给出这样一种解法。

思路3:(1)输入整数到变量N;声明一个数组A[N+1](有些古早的编译器不允许在程序中用变量做为数组的长度来声明数组,这里也可同一声明为A[10]),把第二行的N个数一次读入到数组A中;输入要插入的整数到变量X。给变量flag赋值为N,这里的N用来标记要插入的位置。

(2)遍历数组的每个元素A[i],当遇到第一个i,使得 x<A[i] ,标记flag=i,并跳出循环。

(3)让i从N开始,把A[i-1]赋值给A[i],直到i=flag。执行完这一步,想让与让数组从下标为flag的元素开始整体向右游动一位。

(4)把X赋值给A[flag],这时就完成了插入。

代码3:

#include <stdio.h>
int main () {
    int N,i,X,flag; // 用flag记录要插入的位置
    scanf("%d", &N);
    int A[N+1];
    flag = N;       // 默认插入最后
    for (i = 0; i < N; i++) {  // 输入原始数组
        scanf("%d", &A[i]);
    }
    scanf("%d", &X);           // 输入要插入的元素
    for (i = 0; i < N; i++) {
        if (X < A[i]) {       // 第一个使得A[i]>X的位置i,就是要插入的位置
            flag = i;     
            break;
        }
    }
    for (i = N; i > flag; i--) {  // 从要插入的位置之后所有元素向后移动一位
        A[i] = A[i-1];
    }
    A[flag] = X;                  // 把新元素插入
    for (i = 0; i < N+1; i++) {   // 输出即可
        printf("%d ", A[i]);
    }
    return 0;
}

代码3这种办法的一个好处就是,很容易在外面套一层循环,把它扩展成一种排序算法--插入排序。

思路4:还有一种方法就是,声明数组A[N+1],把要插入的数X赋值给A[N],然后对数组A进行一个选择排序或者冒泡排序。这种方法就属于杀鸡焉用牛刀,不推荐。

代码4:

#include <stdio.h>
int main () {
    int N,i,j,tmp;
    int A[10];
    scanf("%d\n", &N);
    for (i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }
    scanf("%d", &A[N]);
    for (i = 0; i < N; i++) {          // 选择排序
        for (j = i+1; j < N+1; j++) {
            if (A[i] > A[j]) {
                tmp = A[i];
                A[i] = A[j];
                A[j] = tmp;
            }
        }
    }
    // for (i = 0; i < N; i++) {      // 冒泡排序
    //     for (j = 0; j < N-i; j++) {
    //         if (A[j] > A[j+1]) {
    //             tmp = A[j];
    //             A[j] = A[j+1];
    //             A[j+1] = tmp;
    //         }
    //     }
    // }
    for (i = 0; i < N+1; i++) {
        printf("%d ", A[i]);
    }
    return 0;
}
更多PTA题目的的参考代码,可以在wx小程序里搜“PTA刷题助手”,或扫下面的二维码

本题要求编写程序,将一个给定的整数插到原本有序的整数序列中,使结果序列仍然有序,PTA编程题解析,c语言,算法文章来源地址https://www.toymoban.com/news/detail-771008.html

到了这里,关于PTA 编程题(C语言)-- 简化的插入排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • PTA 编程题(C语言)-- 输出闰年

    输出21世纪中截止某个年份以来的所有闰年年份。注意:闰年的判别条件是该年年份能被4整除但不能被100整除、或者能被400整除。 输入格式: 输入在一行中给出21世纪的某个截止年份。 输出格式: 逐行输出满足条件的所有闰年年份,即每个年份占一行。输入若非21世纪的年份则

    2024年02月05日
    浏览(48)
  • 【PTA-C语言】编程练习4 - 数组Ⅱ

    如果代码存在问题,麻烦大家指正 ~ ~ 有帮助麻烦点个赞 ~ ~ 作者 李民 单位 武汉理工大学 本题模拟2048游戏的规则,提供4X4个格子,输入每个格子的初始值(空白格子值为0),玩家选择向下移动,所有数字向下靠拢,相同的数字相撞时会合并。移动结束后,输出合并后的数值

    2024年02月03日
    浏览(45)
  • 【PTA-C语言】编程练习4 - 数组Ⅰ

    如果代码存在问题,麻烦大家指正 ~ ~ 有帮助麻烦点个赞 ~ ~ 作者 翁恺 单位 浙江大学 班级里要搞智力竞赛啦!同学们都踊跃参加。进入最后决赛的是10个同学,随着一道道题目的出示,有时是1号选手得分,有时是5号选手得分,每次答对者得10分,最后结果如何呢? 输入格式:

    2024年02月03日
    浏览(45)
  • PTA 编程题(C语言)-- 查找指定字符

    题目标题:查找指定字符          题目作者:颜晖 浙江大学 本题要求编写程序,从给定字符串中查找某指定的字符。 输入格式: 输入的第一行是一个待查找的字符。第二行是一个以回车结束的非空字符串(不超过80个字符)。 输出格式: 如果找到,在一行内按照格式“

    2024年02月04日
    浏览(35)
  • 【排序算法】插入排序(C语言)

    【排序算法】—— 插入排序 ​ 直接插入排序是一种简单的插入排序法,对数组进行一个遍历,每次都对待排的数据按照大小顺序插入到一个有序数组中的特定位置,直到所有的数据全部插入完毕,就得到一个有序数列。 ​ 插入排序的算法非常简单,依次对每一个元素进行

    2024年01月23日
    浏览(42)
  • Halide 高效的图像处理语言 简化图像编程

    github源码 Halide是用C++作为宿主语言的一个图像处理相关的DSL(Domain Specified Language)语言,全称领域专用语言。 主要的作用为在软硬层面上(与算法本身的设计无关)实现对算法的底层加速,我们有必要对其有一定的了解。 因为不论是 传统的图像处理方法亦或是深度学习应用 都使

    2024年04月26日
    浏览(43)
  • 【PTA-C语言】编程练习3 - 循环结构Ⅱ

    如果代码存在问题,麻烦大家指正 ~ ~ 有帮助麻烦点个赞 ~ ~ 给定两个均不超过9的正整数a和n,要求编写程序求a+aa+aaa++⋯+aa⋯a(n个a)之和。 输入格式: 输入在一行中给出不超过9的正整数a和n。 输出格式: 在一行中按照“s = 对应的和”的格式输出。 输入样例: 输出样例:

    2024年02月03日
    浏览(53)
  • PTA 编程题(C语言)-- 水仙花数

    题目标题:水仙花数             题目作者:徐镜春  浙江大学 水仙花数是指一个N位正整数(N≥3),它的每个位上的数字的N次幂之和等于它本身。例如:153=1^3+5^3+3^3。 本题要求编写程序,计算所有N位水仙花数。 输入格式: 输入在一行中给出一个正整数N(3≤N≤7)。 输出

    2024年02月04日
    浏览(105)
  • PTA 编程题(C语言)-- 高速公路超速处罚

     题目作者:陈建海  浙江大学 按照规定,在高速公路上行使的机动车,达到或超出本车道限速的10%则处200元罚款;若达到或超出50%,就要吊销驾驶证。请编写程序根据车速和限速自动判别对该机动车的处理。 输入格式: 输入在一行中给出2个正整数,分别对应车速和限速,其

    2024年02月08日
    浏览(44)
  • 给定一个n×n的方阵,本题要求计算该矩阵除副对角线、最后一列和最后一行以外的所有元素之和。

    给定一个n×n的方阵,本题要求计算该矩阵除副对角线、最后一列和最后一行以外的所有元素之和。副对角线为从矩阵的右上角至左下角的连线。 输入格式: 输入第一行给出正整数n(1n≤10);随后n行,每行给出n个整数,其间以空格分隔。 输出格式: 在一行中给出该矩阵除副

    2024年02月05日
    浏览(60)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包