算法第四章实践报告|实践题解(代码片段)

关键词：

算法第四章实践报告

一、实践题目：7-2 删数问题

二、问题描述

给定n位正整数，去掉其中任意k <= n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。

三、算法描述

1．解法一：参考链接如下

https://blog.csdn.net/cqs_experiment/article/details/16975003

2．解法二：对于给定的一串数字，每次删除第一个左边大于右边的数字，若完全升序则删除最后一个数字，删除k次即可。输出结果的时候注意去掉前导0。

3．代码如下：

（1）删除数字

while(s > 0) 
    i = 0;
    len = strlen(a);
    
    while (i < len && a[i] <= a[i+1]) 
        // 遍历a[i]，直到找出a[i] > a[i+1]的a[i] 
        i++;
    
    while (i < len) 
        // 移动数组元素 
        a[i] = a[i+1];
        i++;
    
    s--;
    // 重新寻找 

（2）输出不含前导0

i = 0;
len = strlen(a);
while (a[i] == ‘0‘ && i < len) 
    i++;

四、算法时间及空间复杂度分析（含分析过程）

1．遍历次数n x 迁移次数n，时间复杂度：O(n)。

2．空间复杂度（只有原先存储输入数据的数组）：O(1)

五、心得体会（实践收获及疑惑总结）

1．实践收获：

这次实践作业是在上课时间开放的，时间控制提高了编程的强度。

对于具有明显的贪心选择性质的题目，采用贪心算法能快速解决问题，如题7-3。

对于特定的贪心算法，还可以从时间/空间复杂度入手对其进行优化，如题7-1对于新数组元素的记录。

2．疑惑总结：

7-1、7-3较水，具有明显的贪心选择。个人感觉其实在做题的时候还需要严格证明一下贪心算法的正确性。

六、参考链接

1．https://blog.csdn.net/plain_maple/article/details/53426867

2．https://www.cnblogs.com/xiaoying1245970347/p/4630399.html

算法第四章实践报告(代码片段)

1、实践题目   7-1最优合并问题2、问题描述       给定k个排好序的序列,用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较。试... 查看详情

算法第四章实践报告(代码片段)

1.实践题目     7-1 最优合并问题 2.问题描述给定k个排好序的序列,用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较。试设计一个算法确... 查看详情

算法第四章上机实践报告(代码片段)

1.实践题目     7-1 最优合并问题 2.问题描述给定k个排好序的序列,用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较。试设计一个算法确... 查看详情

算法第四章实践报告(代码片段)

1.实践题目    程序存储问题2.问题描述    设有n个程序1,2,…,n要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1≤i≤n。程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得能... 查看详情

算法第四章上机实践报告(代码片段)

一、实践题目：删数问题二、问题描述：    给定一个n位的正整数a，去掉其中任意k（k≤n）个数字后，剩下的数字按照原次序排列成一个的新的正整数。在给定的n位正整数a和正整数k的情况下，输出完成该操作后... 查看详情

算法第四章上机实践报告(代码片段)

一、实践题目：最优合并问题二、问题描述：给定k个排好序的序列,用2路合并算法将这k个序列合并成一个序列。设所采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较，　　求最多比较次数和最少比较次数。三、... 查看详情

算法第四章实践报告(代码片段)

1.选择第二题进行分析。给定n位正整数a，去掉其中任意k≤n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。输入1785434输出132.... 查看详情

算法第四章实践报告(代码片段)

一.实践题目7-3程序存储问题二.问题描述设有n个程序1,2,…,n要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1≤i≤n。程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序... 查看详情

算法第四章上机实践报告(代码片段)

 1.实践题目　　程序存储问题2.问题描述　　设有n个程序1,2,…,n要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1≤i≤n。程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能... 查看详情

第四章实践报告(代码片段)

1.实践题目删数问题 2.问题描述给定n位正整数a，去掉其中任意k≤n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。输入格... 查看详情

第四章实践报告(代码片段)

7-1最优合并问题1.问题描述:给定k个排好序的序列,用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需... 查看详情

第四章上机实践报告(代码片段)

一:实践题目: 删数问题 （110分）给定n位正整数a，去掉其中任意k≤n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。输... 查看详情

第四章实践报告(代码片段)

1.实践题目第三题（程序存储问题 ）2.问题描述设有n个程序1,2,…,n要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1≤i≤n。程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可... 查看详情

算法第四章上机实践报告

1、实践题目     删数问题2、问题描述   给定n位正整数a，去掉其中任意k≤n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组... 查看详情

算法第四章实践报告

1.实践题目程序存储问题2.问题描述设有n个程序1,2,…,n要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1≤i≤n。程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。对... 查看详情

算法第四章实践报告

1、实践题目  删数问题2、问题描述   给定n位正整数a，去掉其中任意k≤n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小... 查看详情

算法第四章实践报告

1、实践题目：程序存储问题2、问题描述：设有n个程序1,2,…,n要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1≤i≤n。程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程... 查看详情

第四章实践报告

第四章实践报告实践报告任选一题进行分析。内容包括：实践题目：程序存储问题问题描述：设有n个程序1,2,…,n要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1≤i≤n。程序存储问题要求确定这n个程序在磁带上的一... 查看详情