算法第四章上机实践报告

本文主要是介绍算法第四章上机实践报告，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1.题目：删数问题

给定n位正整数a，去掉其中任意k≤n 个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数 k，设计一个算法找出剩下数字组成的新数最小的删数方案。如果数字最前面有0不输出。

输入格式：第 1 行是1 个正整数 a。第 2 行是正整数k。

输出格式：输出最小数。

    输入样例：                输出样例：

2.贪心选择性质

2.1 思路

题目要求的是删除k个数字之后的最小数，假设输入序列的个数为n，本题可以转化为：在输入序列中取n-k个数构成最小数。我们每次取的构成最小数的数值就是当前序列的最小值，由于取出的数要按原次序排列，所以本题要考虑以下两种情况：

①选择当前序列的最小值后，最小值后面序列的个数小于我们还需要的数。这种情况我们就要舍弃掉第一小的数，选择第二小的数判断是否符合条件，若不符合继续去第三小的数，以此类推，直到找到符合条件的数，break退出。

②选择当前序列的最小值后，最小值后面序列的个数大于或等于我们还需要的数。这种情况当然就是我们需要的啦。

考虑以上两种情况之后，还要注意，第一位数值若为0，不能输出。

2.2 代码

#include <iostream>

#include <string.h>

#include <algorithm>

using namespace std;

char a[1000];

struct Num{

int arr;//数值

int brr;//下标

};//弄个结构体是为了快速排序的时候可以返回下标

Num num[1000];

Num num2[1000];//因为快速排序之后num会变成快排之后的序列，用num2保留原本序列

int k;

bool cmp(Num x,Num y){

if(x.arr==y.arr){

return x.brr<y.brr;

}

return x.arr<y.arr;

}

//快速排序

int vv(Num aa[],int start,int end,int min){

sort(aa+start,aa+end,cmp);

return aa[min].brr;

} //弄个min是为了能够找到第二小、第三小...的数

int main() {

cin>>a;

cin>>k;

int n=strlen(a);//求出a的长度

bool cc=false;//一开始还没输出，初始值设为false

for(int i=0;i<n;i++){

num[i].arr=a[i]-48;

num[i].brr=i;

}//a是个字符数组，这里把它转成整型数组

for(int i=0;i<n;i++){

num2[i].arr = num[i].arr;

num2[i].brr = num[i].brr;

}//复制

int w=n-k;//需要找几次

for(int i=0;i<w;i++){

int min = 0;

int result = vv(num,0,n,min);

//如果找到的数符合要求

if(n-1-result >= w-i-1){

//为0，但不是第一个

if(num2[result].arr==0&&cc==true){

cout << num2[result].arr;

}else{  //不为0

if((num2[result].arr)!=0){

cout << num2[result].arr;

cc=true;//记得设为已经有输出了

}

}

n=n-result-1;//取得符合条件得数后，序列就变成该数后面的序列了

for(int ii=0;ii<n;ii++){

num[ii].arr = num2[ii+result+1].arr;

num[ii].brr = ii;

num2[ii].arr = num[ii].arr;

num2[ii].brr = num[ii].brr;

}

}else{//不符合要求，循环找到符合要求的，类似上面

for(min=1;min<n;min++){

int resultt = vv(num,0,n,min);

if(n-1-resultt >= w-i-1){

if(num2[resultt].arr==0&&cc==true){

cout<<num2[resultt].arr;

}else{

if((num2[resultt].arr)!=0){

cout<<num2[resultt].arr;

cc=true;

}

}

n=n-resultt-1;

for(int iii=0;iii<n;iii++){

num[iii].arr = num2[iii+resultt+1].arr;

num[iii].brr = iii;

num2[iii].arr = num[iii].arr;

num2[iii].brr = num[iii].brr;

}

break;

}

}

}

}

return 0;

}

3.时间复杂度分析

时间复杂度应该是O(n*(n-k))

理由：本题要找n-k次，找到合适的数值后都要遍历复制数组，平均时间复杂度为n/2，综合起来时间复杂度为：O(n*(n-k))——取决于k的大小，若k很小的话，约等于O(n^2)

4.对贪心算法的理解

在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的“局部最优解”。

因此贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。

5.疑难杂症

还有一种输入方法，为什么已经用long long int，足够长了还不让我过PINTIA，所有输入样例都过了，就是PINTIA不让我过。

不过用long long int的方式定义a，输入后再转成数组会导致倒序，代码写起来有点复杂。以下就是long long int的方式定义a的代码：

#include <iostream>

#include <algorithm>

using namespace std;

long long int a;

long long int k;

struct Num{

int arr;//数值

int brr;//下标

};

Num num [1000];

Num num2 [1000];

bool cmp(Num x,Num y){

if(x.arr==y.arr){

return x.brr<y.brr;

}

return x.arr<y.arr;

}

//快速排序

int vv(Num aa[],int start,int end,int min){

sort(aa+start,aa+end,cmp);

return aa[min].brr;

}

int main() {

cin>>a;

cin>>k;

int n=0;

bool cc=false;

while(a!=0){

num[n].arr=a%10;

a=a/10;

n=n+1;

}//求得共有n个数

for(int i=n-1;i>=0;i--){

num[i].brr=n-1-i;

}

for(int i=0;i<n;i++){

num2[i].arr = num[i].arr;

num2[i].brr = num[i].brr;

}

//总共要找几次

int w=n-k;

for(int i=0;i<w;i++){

int min=0;

int result = vv(num,0,n,min);

//如果找到的数符合要求

if(n-1-result >= w-i-1){

//为0，但不是第一个

if((num2[n-1-result].arr)==0&&cc==true){

cout << num2[n-1-result].arr;

}else{  

if((num2[n-1-result].arr)!=0){

cout << num2[n-1-result].arr;

cc=true;

}

}

for(int i=0;i<n-1-result;i++){

num[i].arr = num2[i].arr;

num[i].brr = n-result-2-i;

}

n=n-result-1;

}else{//不符合要求

for(min=1;min<n;min++){

int resultt = vv(num,0,n,min);

if(n-1-resultt >= w-i-1){

if((num2[n-1-resultt].arr)==0&&cc==true){

cout<<num2[n-1-resultt].arr;

}else{

if((num2[n-1-resultt].arr)!=0){

cout<<num2[n-1-resultt].arr;

cc=true;

}

}

for(int i=0;i<n-1-resultt;i++){

num[i].arr = num2[i].arr;

num[i].brr = n-resultt-2-i;

}

n=n-resultt-1;

break;

}

}

}

}

return 0;

}

这篇关于算法第四章上机实践报告的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！