/*日期:2011-10-21
作者:xiaosi
题目: 数列极差问题(贪心)
*/
#include<iostream>
#include<cstdio>
#include<stdlib.h>
#include<math.h>
using namespace std;
#define Maxint 999999
#define Minint -1
int progression[2001];
int progression1[2001];
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
int Max(int progression[],int n)
{
int i,j,a,b,max;
for(i=0;i<n-1;i++)//求max
{
a=0;b=1;
for(j=2;j<n;j++)
{
if(progression[j]<progression[a]||progression[j]<progression[b])
{
if(progression[a]>progression[b])
{
a=j;
}
else
{
b=j;
}
}
}
max=progression[a]*progression[b]+1;
progression[a]=max;
progression[b]=Maxint;
}
return max;
}
int Min(int progression[],int n)
{
int i,j,a,b,min;
for(i=n-2;i>=0;i--)//求min
{
a=n-2;b=n-1;
for(j=n-3;j>=0;j--)
{
if(progression[j]>progression[a]||progression[j]>progression[b])
{
if(progression[a]<progression[b])
{
a=j;
}
else
{
b=j;
}
}
}
min=progression[a]*progression[b]+1;
progression[a]=min;
progression[b]=Minint;
}
return min;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int min,max,M,num,i,j;
for(i=0;i<n;i++)
{
scanf("%d",&progression[i]);
}
qsort(progression,n,sizeof(progression[0]),cmp);
for(i=0;i<n;i++)
{
progression1[i]=progression[i];
}
max=Max(progression,n);
//min=Min(progression1,n);
min=1;
for(i=n-1;i>=0;i--)
{
min=min*progression1[i]+1;
}
M=max-min;
if(M==0)
{
num=1;
}
else
{
num=(int)log10(M)+1;
}
printf("%d\n%d\n",num,M);
}
return 0;
}
分享到:
相关推荐
算法分析与设计数列极差问题。还不错的程序,希望大家多多支持啊
利用贪心思想实现数列极差问题,visual stdio sp1下编译通过,并可运行。
数列极差问题:给定n个正整数数列,进行如下操作:每次删去两个数 a和b,添加1个数 a*b+1,直到只剩1个数N。在所有的这样的N中,有1个最大Max的和最小的Min,M=Max-Min是极差,设计程序计算M。
在黑板上写n个正整数排成一个数列,进行如下操作:每次擦去其中两个数a和b,然后在数列中的加入一个数a×b+1,如此下去,直至黑板上剩下一个数,在所有按这种操作方式最后得到的数中...则该数列的极差定义为M=max-min。
数列极差数代码
算法-数列极差(信息学奥赛一本通-T1427).rar
贪心算法的基本思路: 从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时,算法停止。
工具VS2010,循环结构语句实现等差数列输出前n项元素,以及求解并输出它们的和,利用textBox1输入n的值。等差数列的数据可以改。
2020_2021学年高中数学第一章数列2等差数列第3课时等差数列的前n项和练习含解析北师大版必修5
用c++语言解数据结构中的斐波那契数列问题。
等差数列.doc
高中数学数列等差数列的前n项和北师大必修PPT课件.pptx
等差数列JAVA,JAVA编程语言的的等差数列
c#控制台编写的等差数列计算,供初学者参考,希望你们有进步
分式线性递推数列通项的矩阵求法[归纳].pdf
数列通项公式常用求法及构造法.doc
线性递推数列通项公式的求法 对做数列题有很大的帮助 对高中生来说是一笔宝贵的财富 希望大家喜欢
四年级举一反三最优化问题等差数列.ppt
2009高考数列总复习 2009高考 数列 总复习 ...9、求数列通项的两个途径 10、数列解答题的常见题型及解题策略 内容十分丰富全面!! 注:其中的caj文件需要用CAJViewer软件打开,pdf文件需要用Adobe Reader软件打开。
EE课程 数列递增子序列 数据与算法 实验报告