首页 > 代码库 > 算法课作业之删数问题

算法课作业之删数问题

问题描述:

通过键盘输入一个高精度的正整数n(n的有效位数≤240),去掉其中任意s个数字后,剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s,寻找一种方案,使得剩下的数字组成的新数最小。

 

问题分析:

这个问题是最优子结构问题,即局部最优能决定全局最优解,可以使用贪心算法进行解决。n个正整数去掉s个数字,求使得到的新的正整数最大的删除方案可以等价为:对于n个正整数组成的数字,一个一个地依次去掉s个数字,要求每删除一个数时,都使删除后的新的正整数最小。因此问题转化为求解删除一个数字时是新的数字最小的方案,求得这个方案后只需要对其执行s次即可。

因为删数后剩下的数字原左右次序不变,所以要尽可能在左边删除,我们从左往右进行考虑,假设n个整数为a(1),a(2)....a(n),当由左往右第一次出现a(k)>a(k+1),可以发现,①删除任何一个a(k)之前的元素得到的新数都比删除a(k)得到的新数大,所以可以明确a(k)之前的元素可以排除;②倘若删除a(k),则新的数字第k位变成a(k+1),记这个新的数字为c,倘若删除a(k)之后的任何一位,得到的新的数字第k位仍然是a(k),记这个新的数字为d。比较c和d,可以发现,c(1)=d(1),......,c(k-1)=d(k-1),因为a(k)>a(k+1),所以c(k)<d(k),那么有c<d。综上可知,对于数字a,应该删除由左往右第一次出现a(k)>a(k+1)时的a(k),如果a的数字序列一直是非减的,那么删除最后一位即可。

本算法的完整C++代码如下:

#include "stdafx.h"#include "vector"#include "cmath"#include "iostream"using namespace std;int digit_to_int(char d)//将char数组中的元素转换为整数以便于进行比较{    char str[2];    str[0] = d;    str[1] = /0;    return (int)strtol(str, NULL, 10);}

void DeleteOneBit(char * a,int _size){//每次只删除一位的函数 int i = 0; bool _is = false;//用于判断是否需要将部分右边的元素左移一位 while (i < _size - 1){ if (digit_to_int(a[i])>digit_to_int(a[i+1])){ _is = true; break;} i++; } if (_is){ for (; i < _size - 1;i++) { a[i] = a[i + 1]; } } a[_size - 1] = \0;//写终止符 }
void GetNewNum(char* b,int _num_d){ int _lenght = strlen(b); if (_num_d>=_lenght){ cout << "删除的位数过多" << endl; return;} for (int i = 0; i < _num_d;i++){ DeleteOneBit(b, _lenght); _lenght--; } }int _tmain(int argc, _TCHAR* argv[]){ cout << "请输入要进行删数的正整数(小于240位)"<<endl; char a[241]; cin >> a; int _num_d; cout << "请输入要删除的位数(小于输入的整数的位数)" << endl; cin >> _num_d; GetNewNum(a, _num_d); cout << a; system("pause"); return 0;}

 

算法课作业之删数问题