对于给定的整数,求出删除该整数中的一个数字后得到的最小值.
比如,1214 ,去掉2,得到的结果是114为最小值.
算法: 删除数字中的极大值( 左边的数字递增,右边紧邻的数字是减少的或者本身为最后一位。例如:1214 中的2 ; 122543中的5; 1334中的4)
证明:假设极大值为第i位,记为X[i].分2种情况,
1 。如果删除 i 左边的某位记第j位,即删除X[j]
删除前 ----jj+1---i----
删除 X[j] 后 ----j+1---i---
删除 X[i] 后 ----j ----------
因为i左边的是递增的,X[j] < x[j+1] , 删除X[j]后的值 比删除X[i] 的值大。 故 不可能删除比i左边的某位
2。 如果删除i 右边的某位,i 左边的那些位保持不变,而删除X[i]后,相比不删除X[i],X[i+1] 取代了X[i]的位置;而由于
X[i+1] < x[i] 的,所以删除X[i] 比 删除i 右边其他的任何一位都要小。
综上,故需要删除第i位。(极大值的那一位)
代码如下:(估计有更好的代码,如有请留言给我O(∩_∩)O谢谢)
#include <vector>
#include <iostream>
using namespace std;
void int_to_array(int N, vector< int > & A)
{
while(N)
{
A.push_back( N % 10);
N = N / 10;
}
}
int find_min(const int& N)
{
if( N>=0 && N <10) return 0;
vector< int > iv;
int_to_array(N, iv);
vector<int>::iterator ite = iv.end();
--ite;
//删去极大值(比左边所有位大,比右边紧邻着的一位小)
//vector end 1214 begin 删除2
for(;;)
{
if(ite == iv.begin() || *ite > *(ite-1)) //从左到右找到第一个比右边大的那一位,若没找到就是最右边一位
{
iv.erase(ite);
break;
}
--ite;
}
//把vetor转为int
int M = 0;
for(ite = iv.end() - 1; ; --ite)
{
M =M * 10 + *ite;
if(ite == iv.begin()) break;
}
return M;
}
int main()
{
for(int i = 500; i < 1000; i= i + 3)
{
cout<<"原来:"<< i << "减去一位"<< find_min(i)<<endl;
}
return 0;
}
分享到:
相关推荐
任意给定 n 个整数,求这 n 个整数序列的和、最小值、最大值 输入描述 输入一个整数n,代表接下来输入整数个数,n,接着输入n个整数,整数用int表示即可。 输出描述 输出整数序列的和、最小值、最大值。用空格隔开...
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
给定n 个整数组成的序列,编程计算该序列的最优m 段分割,使m 段子序列的和的最大值达到最小。 Input 输入由多组测试数据组成。 每组测试数据输入的第1行中有2个正整数n和m。正整数n是序列的长度;正整数m是分割...
给定一个整数数组,其中元素的取值范围为0到10000,求其中出现次数最多的数。
从键盘任意输入10个整数,用指针变量作函数参数编程计算最大值和最小值,并返回它们所在数组中的位置。
输入在第一行中给出一个正整数n(1≤10)。第二行输入n个整数,用空格分开。 输出格式: 在一行中输出最大值及最大值的最小下标,中间用一个空格分开。 输入样例: 6 2 8 10 1 9 10 输出样例: 10 2
输入两个数求最大值最小值用Java编写一个应用程序,对程序中给定的两个整数,求其最大值和最小值,并把它们输出。 编写一个应用程序,给定两个正整数,求出它们之间的最大公约数,如6和8的最大公约数为2,8和12的...
在一个按照东西和南北方向划分成规整街区的城市里,n个居民点散乱地分布在不同的街区中。用x 坐标表示东西向,用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。街区中任意2 点(x1,y1)和(x2,y2)之间的距离...
给定一个精确整数,用分治法删除两个最大数两个最小数。
产生n个1~1000之间的随机整数(n=10,100,1000),求其中的最大数和最小数的值及其所在位置,同时要求统计处理过程中实际数据比较次数
编写一个Java程序,找到并输出一个整数数组中的最大值和最小值。 编写一个Java程序,实现冒泡排序算法对一个整数数组进行排序。 编写一个Java程序,读取一个文本文件,并统计文件中每个单词的出现次数。 编写一个...
问题描述 给定 N 个整数,请你找出这 N 个数中最大的那个和最小的那个。 输入格式 第一行包含一个正整数 N 。(1 ≤ N ≤ 10000)。 第二行为 N 个用空格隔开的整数,每个数的绝对值不超过 1000000。 输出格式 输出...
给定一个长度为n的非负整数序列,请计算序列的最大跨度值(最大跨度值 = 最大值减去最小值)。 【输入】 一共2行,第一行为序列的个数n(1 ≤ n ≤ 1000),第二行为序列的n个不超过1000的非负整数,整数之间以一个...
给定一组正整数,其中的最大值和最小值分别为max和min,其中的一个数x到max和min的距离差D定义为 abs(abs(x-max) - abs(x-min))。 其中,abs()表示求一个数的绝对值 输入 输入第一行为整数n,剩余n行每行一个正...
编写一个程序,估算所给出n个实数的均值Mean、方差Variance和标准差StdDeviation。 其中: 均值指这些数字的平均值。 计算标准差的公式如下: 这里的σ(x1,…,xn)是x值的标准差,xavg则是这n个值的均值。 ...
50006 使用函数统计一个整数中数字的个数 45 50007 使用函数找水仙花数 46 50009 使用函数求余弦函数的近似值 48 50052 使用函数找最大值 49 50062 使用函数输出指定范围内的 Fibonacci 数 50 50063 使用函数找出...
如何求出一个人到某指定日期的周岁? 计算距离退休年龄的公式 求工齡 计算工龄 年龄及工龄计算自动算出工龄日期格式为(yyyy.mm.dd) 【时间和日期应用】 自动显示当前日期公式 如何在单元格中自动填入当前日期 如何...
给定一个整数n,对其进行因子分解,统计其有多少种不同的分解方法,并给出所有的分解方法。 输入要求: 输入整数n,占1行。 输出要求: 输出的第1行为一个整数,即该整数有多少种因子分解方法。其后有若干行,分别...
问题描述 给定一个算式,该算式中只含一个四则运算符号,操作数及结果均为整数。要求判断该算式的正确性(规定:除法必须除尽才算正确)。 输入 输入数据有若干行,每行上有一个算式,对应一种情形。 输出 对于每一...
如何求出一个人到某指定日期的周岁? 计算距离退休年龄的公式 求工齡 计算工龄 年龄及工龄计算自动算出工龄日期格式为(yyyy.mm.dd) 【时间和日期应用】 自动显示当前日期公式 如何在单元格中自动填入当前日期 如何...