删数问题(C语言实现)
删数问題 输入一个高精度的正整数n(≤200位)去掉其中任意k个数字后剩下的数字按照原来的左右次序组成一个新的正整数。编程对给定的n与k寻找一种方案,使得剩下的数字组成的新数最小
想要删除之后的数字最小,我们需要用到贪心算法策略先达到局部最优进而达到整体最優。
结合测试数据来说在178542中删除第一个数字之后使他成为删掉一个数字之后的最小值,首先要知道这个数字原来是6位数删掉一个数字之后使5位数,而在相同尾数下决定一个数字的大小的应该是先比较首位数字进而比较第二位数字,然后下一位以此類推。
所以当删除第一个数字的时候主需要考虑是丢掉数组下标为0的还是下标为1的内容。为了方便进行处理并不是直接输入一个數字,而是输入一个字符串数组
结合测试数据,第一次需要去掉的数字是7因为去掉1之后是78542, 去掉7之后是18542只根据首位数字便可比较出大小。删掉比较小的数字后将其他下标的内容往前移动即可
第二次及需要去掉的数字是8,可以将去掉1和去掉8之后的数字进行比较
以此类推,直到数字长度达到要求
一开始并不是定义的char 类型数组,而是int 类型
当輸入完测试数据之后还要据需输入。
思考后发现因为我们输入的数字178542是连续输入的所以程序会认为我们只输入了一个数字洏已。如果要定义为int类型的数组标准的输入应该是 1 7 8 5 4 2 , 中间需要加空格以表示数字的区分但是定義为char类型则很方便数据的输入与表示。