【题目】
在由N个正整数的集合S中,找出最大元素C,满足C=A + B其中A,B都是集合S中元素,请给出算法描述,代码与时间复杂度分析。
【分析】
1,对集合S进行排序(快排),从小到大排序
2,让C指向集合最后一个元素(最大元素)
3,让i指向S中第一个元素,让j指向C的前一个元素
4,如果,A[i]+A[j]==C则return C;
5,如果if(A[i]+A[j]<C)则i++;
6,如果if(A[i]+A[j]>C)则j--;
7,直道i>=j依然没有找到符合条件的元素,则C在S中向前移动一位,跳至步骤3
【代码】
/*********************************
* 日期:2015-01-29
* 作者:SJF0115
* 题目: 在由N个正整数的集合S中,找出最大元素C,满足C=A+B,其中A,B都是集合S中的元素
* 来源:百度
* 博客:
**********************************/
#include <iostream>
#include <algorithm>
using namespace std;
int FindSum(int A[],int n){
// 排序
sort(A,A+n);
int left,right,sum;
// i = C
for(int i = n - 1;i >= 2;--i){
left = 0,right = i - 1;
// 判断是否有A + B = i
while(left < right){
sum = A[left] + A[right];
if(sum == A[i]){
return A[i];
}//if
else if(sum > A[i]){
--right;
}
else{
++left;
}
}//while
}//for
return -1;
}
int main(){
int A[] = {5,7,3,0,9,11,8,13,100};
int n = 9;
cout<<FindSum(A,n)<<endl;;
return 0;
}
讨论:[百度]在由N个正整数的集合S中,找出最大元素C,满足C=A + B
分享到:
相关推荐
将正整数n表示成一系列正整数之和:n=n1+n2+…+nk,其中n1≥n2≥…≥nk≥1,k≥1。 正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。 例如正整数6有如下11种不同的划分: 6; 5+1; 4+2,4+1+1...
对于给定的正整数的集合S={x1,x2,...,xn}和正整数c,编程计算S 的一个子集 S1,使得x∈S1,∑x=c. Input 由文件input.txt 提供输入数据。文件第1 行有2 个正整数n 和c,n 表示S 的大小,c 是子集和的目标值。接...
求满足1+2+3+…n的最大正整数n的MATLAB程序
C语言程序设计-找出一批正整数中的最大的偶数;
C语言程序设计-编写函数fun求sum=d+dd+ddd+……+dd...d(n个d),其中d为1-9的数字;例如:3+33+333+3333+33333(此时d=3,n=5),d和n在主函数中输入;
C++,输入两个正整数a和n,求a+aa+aaa+…+aa…a(n个a)之和
对于给定的n位正整数a 和正整数k,设计一个算法找出剩下数字组成的新数 最小的删数方案。 «编程任务: 对于给定的正整数a,编程计算删去k个数字后得到的最小数。 Input 由文件input.txt提供输入数据。文件的第1...
算法设计:对于给定的正整数的集合S={x1,x2,...,xn}和正整数c,计算S的一个子集S1,使得子集里的元素之和为c。 数据输入:由文件input.txt提供输入数据。文件第1行有2个正整数n和c,n表示S的大小,c是子集和的目标值...
设有n个正整数,将他们连接成一排,组成一个最大的多位整数。 如:n=3时,3个整数13,312,343,连成的最大整数为34331213。 如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613。 输入描述: 有多组测试样例,每组...
找出一个整数是哪些个连续整数的和(例如:15=1+2+3+4+5,15=4+5+6,15=7+8)
C语言程序设计-编写程序求无理数e的值并输出;计算公式为:e=1+11!+12!+13!+......+1n!当1n!0.000001时e=2.718282;.c
子集和问题的一个实例为?St?〈St〉。其中,S={x1,x2,…,xn}S={x1,x2,…,xn}是一个正整数的集合,c是一个正整数。子集和问题判定是否存在 S 的一个子集 ...接下来的 1 行中,有 n 个正整数,表示集合 S 中的元素。
分析:求解k个数的不同组合,我们可以用一维数组a[0]~a[k-1]来保存其中的一个结果,因为组合...所以a[k-1]即组合中的最后一个数,只能为k~n 令i=a[k-1] 则 i>=k && i<=n 完整代码请参考我的博客文章,这里只是核心部分
给定一个整数n,求出所有连续的且和为n正整数。比如对于整数27,结果为2~7、8~10、13和14,因为这些数之间的整数的和都是27。注意:并不是所有的整数都有结果,例如不存在连续的整数和为16。为了提高计算的效率,...
第一行为一个整数C,表示有C组测试数据,接下来有2*C行数据,每组测试数据占2行,每组测试数据第一行是1个整数n,表示有n个整数,接下来一行有n个整数,它们之间用空格隔开. Output 你的输出应该有C行,即每组...
第一行2个数:正整数n和整数c。n表示S集合的大小,c是子集和的目标值,接下来一行中,有n个整数,表示集合S中的元素。 Output 将子集和问题的解输出,当无解时,输出"No Solution"(注意No Solution的大小写,空格...
设a 和b是2 个正整数,a≤b,找出a 和b之间约数个数最多的数x。 算法设计: 对于给定的2 个正整数a <= b 计算a 和b之间约数个数最多的数。 可以保证a和b都不超过2000000. 数据输入: 输入数据有2个正整数a和b。 ...
设a 和b 是2 个正整数,a≤b,找出a 和b之间约数个数最多的数x。 编程任务:对于给定的2 个正整数a≤b,编程计算a 和b 之间约数个数最多的数。 Input 输入数据的第1 行有2 个正整数a和b。 Output 程序运行结束时...
a,b,c,d)使得abcd满足等式 其中abcd在1—100之间且b<=c<=d 输入一个正整数N 每行输出一个完美立方 格式为 Cube = a, Triple = (b,c,d) abcd所在位置分别用实际求出四元组值代入。 按照a的值从小到大一次输出,a的值...
给定两个均不超过9的正整数a和n,要求编写程序求a+aa+aaa++⋯+aa⋯a(n个a)之和。