一道java面试题，算法！

Question

1-100中,
求:5个不同数的和小于100的不重复组合的个数.先谢谢大家了！ 

Answer 1

public class test {
public static void main(String[] args) {
int count = 0 ;

for(int i = 1; i <100; i++ )
for(int j = i + 1; j < 100; j++ )
for( int k = j + 1; k < 100; k++ )
for (int m = k + 1; m < 100; m++ )
for(int n = m + 1 ; n <100; n++ )
if(i + j + k + m + n < 100){
count++;
// System.out.println( i + " " + j + " " 
// + k + " " + m + " " + n + " sum:" + (i + j + k + m + n) );
}
System.out.println(count);
}
}

Answer 2

晕~~ 用for循环写，是个人都会，这样效率太差了，
我没说清楚，应该是：求效率比较高的算法。 

Answer 3

不用for,不可能吧,应该用递归

Answer 4

N＝100
随机生成<100的数M1
随机生成<N-M1 的数M2 ，并与判断与M1是否相同 ，相同则相随机生成数
随机生成<N-M1－M2 的数M3 ，并与判断与M1，M2是否相同 ，相同则相随机生成数
随机生成<N-M1－M2-M3 的数M4 ，并与判断与M1,M2,M3是否相同， 相同则相随机生成数
随机生成<N-M1－M2-M3-M4 的数M5 ，并与判断与M1,M2,M3,M4是否相同， 相同则相随机生成数
那么 M1+M2+M3+M4+M5<100

Answer 5

用for，但是可以for小一点范围for (a = 1; a < 90; a++)
    for (b = a+1; b < 94-a; b++)
        for (c = b+1; c < 97-a-b; c++)
            for (d = c+1; d < 99-a-b-c; d++)
                for (e = d+1; e < 100-a-b-c-d; e++)
不知可否实现，请指教。

Answer 6

public class RankNumber { public void test(){
int a1=0,a2=0,a3=0,a4=0,a5=0;
int count= 1;
while(a5<(100-15)){
a5+=1;
++count;
while(a4<a5){
a4+=1;
++count;
while(a3<a4){
a3+=1;
++count;
while(a2<a3){
a2+=1;
++count;
while(a1<a2){
a1+=1;
++count;
}
}
}
}
}
System.out.println(count);
}
        public static void main(String[] args){
Rank r = new Rank();
r.test();
        }
}
运行结果:426.

Answer 7

上传的时候改了下类名.忘记改入口方法里的了.
Rank r=new Rank();
应该为:
RankNumber r = new RankNumber();

Answer 8

public   class   Test3   { 
public   static   void   main(String[]   args)   { 
int   count   =   0   ; for(int i=1;i<86;i++) 
{
for(int   j=i+1;j<(88-i);   j++   ) 
{
for(   int k= j+1;k<(91-i-j);   k++   )
{
for   (int   m   =k+ 1;m<(95-i-j-k);   m++   ) 
{
for(int   n   = m+  1;n<(100-i-j-k-m);   n++   ) 
{
if(i   +   j   +   k   +   m   +   n   <   100)
{ 
count++; 
} 
}
}
}
}
}System.out.println(count); 
} 
}

Answer 9

C# codeusing System;
using System.Collections.Generic;
using System.Text;namespace Test1
{
    class Program
    {
        static void Main(string[] args)
        {
            int total=0;
            int num = 0;            for (int i = 1; i < 18; i++) //第一个数最大只能取到17
                for (int j = i + 1; j < 24; j++) //第二个数最大只能取到23
                    for (int k = j + 1; k < 32; k++) //第三个数最大只能取到31
                        for (int l = k + 1; l < 47; l++) //第四个数最大只能取到46
                        {
                            num++;
                            int m = 99-i-j-k-l;
                            if (m > l)  //第五个数必须大于第四个数
                            {
                                total = total + (m - l); 
                            }
                        }
            System.Console.WriteLine(total); //答案
            System.Console.WriteLine(num);   //循环次数
            System.Console.ReadLine();
        }
    }
}输出：
455175 //答案
84337  //循环次数

Answer 10

另外：13楼 wqs1106 的算法：答案为455175，循环次数为455175。

Answer 11

2楼 imi00 的算法，恩，最直接最原始的算法：答案为455175，循环次数为71523114

Answer 12

public class less100 
{
public static void main(String[] args) 
{
int a1,a2,a3,a4,a5;
int sum=0;
int time=0;
for(a1=1;a1<=17;a1++)
{
for(a2=a1+1;a2<=23;a2++)
{
if((a2*4+6+a1)>=100) break;
else
for(a3=a2+1;a3<=31;a3++)
{
if((a3*3+3+a1+a2)>=100) break;
else
for(a4=a3+1;a4<=46;a4++)
{
if((a4*2+1+a1+a2+a3)>=100) break;
else
{ time++;
                             sum=sum+(99-a1-a2-a3-a4)-a4; } }
}
}
}


System.out.println("结果是"+sum+"   循环次数："+time);
}
}
运行结果：   结果是455175   循环次数： 24260

Answer 13

。。实际上不用这么多if ,我把我原代码的num++;放到if里面就可以了。上面的num++;统计次数统计错了~C#   code using   System; 
using   System.Collections.Generic; 
using   System.Text; namespace   Test1 
{ 
        class   Program 
        { 
                static   void   Main(string[]   args) 
                { 
                        int   total=0; 
                        int   num   =   0;                         for   (int   i   =   1;   i   <   18;   i++)   //第一个数最大只能取到17 
                                for   (int   j   =   i   +   1;   j   <   24;   j++)   //第二个数最大只能取到23 
                                        for   (int   k   =   j   +   1;   k   <   32;   k++)   //第三个数最大只能取到31 
                                                for   (int   l   =   k   +   1;   l   <   47;   l++)   //第四个数最大只能取到46 
                                                { 
                                                        //num++; 放到if里面
                                                        int   m   =   99-i-j-k-l; 
                                                        if   (m   >   l)     //第五个数必须大于第四个数 
                                                        { 
                                                                num++;//这里
                                                                total   =   total   +   (m   -   l);   
                                                        } 
                                                } 
                        System.Console.WriteLine(total);   //答案 
                        System.Console.WriteLine(num);       //循环次数 
                        System.Console.ReadLine(); 
                } 
        } 
} 输出： 
455175   //答案 
24260    //循环次数

Answer 14

从新弄个好看点的C# codeusing System;
using System.Collections.Generic;
using System.Text;namespace Test1
{
    class Program
    {
        static void Main(string[] args)
        {
            int total=0;
            int num = 0;            for (int i = 1; i < 18; i++)
                for (int j = i + 1; j < 24; j++)
                {
                    for (int k = j + 1; k < 32; k++)
                    {
                        for (int l = k + 1; l < 47; l++)
                        {
                            //num++; 放到if 里面
                            int m = 99 - i - j - k - l;
                            if (m > l)
                            {
                                num++;//这里
                                total = total + (m - l);
                            }
                        }
                    }
                }
        
            System.Console.WriteLine(total);
            System.Console.WriteLine(num);
            System.Console.ReadLine();
        }
    }
}

Answer 15

using System;
using System.Collections.Generic;
using System.Text;namespace Test1
{
    class Program
    {
        static void Main(string[] args)
        {
            int total=0;
            int num = 0;            for (int i = 1; i < 18; i++) //第一个数最大只能取到17 
                for (int j = i + 1; j < 24; j++) //第二个数最大只能取到23 
                    for (int k = j + 1; k < 32; k++) //第三个数最大只能取到31
                        for (int l = k + 1; l < 47; l++) //第四个数最大只能取到46 
                        {
                            //num++; 放到if 里面
                            int m = 99 - i - j - k - l;
                            if (m > l)
                            {
                                num++;//这里
                                total = total + (m - l);
                            }
                        }
            System.Console.WriteLine(total);
            System.Console.WriteLine(num);
            System.Console.ReadLine();
        }
    }
}
输出：   
455175       //答案   
24260         //循环次数

Answer 16

难道就没人用递归吗？
int n;
int sum=0;
int j=5;
public Rmath( int m){
if(j!=0){
if(m==1){retrun 1;}else{
n=math.random(100);
sum+=n;
j--;
retrun Rmath(m-sum);
}
}}
大概意思就这样吧
前两天写过一个随机出题的程序  

Answer 17

retrun   Rmath(100-sum);

Answer 18

晕 乱掉了 重来
int   n; 
int   sum=0; 
int   j=5; 
public   Rmath(   int   m){ 
if(j!=0){ 
if(m==1){retrun   1;}else{ 
n=math.random(m); 
sum+=n; 
j--; 
retrun   Rmath(100-sum); 
} 
} }

Answer 19

首先，你这种随机只能随机出一个组合；其次，随机不能保证全部组合都能得到。因为随机有重复性。重复n次random(100），也许会出现几个相同的数字。如果能直接用for来做的话，那就不考虑用递归了，递归效率低，但符合人类思想。

Answer 20

举个例子：random(50)和random（2），说不定都随机出1出来~

Answer 21

随机具有不可预测性，要解决楼主这种有明确答案的问题，random是不能用的

Answer 22

晕，，，要是只求其中的一个组合，用random干吗？直接输出1 + 2 + 3 + 4 + 5 < 100

Answer 23

for (a = 1; a < 18; a++)
    for (b = a+1; b < (94-a)/4; b++)
        for (c = b+1; c < (97-a-b)/3; c++)
            for (d = c+1; d < 99-a-b-c-d; d++){ 
             countNum++;//循环次数
             num=99-a-b-c-2*d;//答案
             count+=num;
            } 
满足条件的个数：454959  循环次数：24118

Answer 24

楼上的不放上来怎么知道那里错拉.之前我的解法错了.
今总结了前面jacaranda,jseasidej的.新修改的后如下.可以计算任意值内的组合.import java.math.BigDecimal;public class RankNumber { public void test(int input_Number){//input_Number 输入的取值范围； int a1,a2,a3,a4;
long count= 0;
int n=input_Number-15;
int c=0;

int n1=this.round((n-1)/5);
int n2=this.round((n-1)/4);
int n3 = this.round((n-1)/3);
int n4 = this.round((n-1)/2);
  
           if(input_Number<15){
            System.out.println("个数为0"); 
           }else{
            for(a1=0;a1<=n1;++a1){
        for(a2=a1;a2<=n2;a2++){
        if(a1+a2*4>=n){
        break;
        }
        for(a3=a2;a3<=n3;a3++){
        if(a1+a2+a3*3>=n){                                          break;
        }
        for(a4=a3;a4<=n4;++a4){
        if(a1+a2+a3+a4*2>=n){
        break;
        }else{                          count = count+(n-a1-a2-a3-a4*2);//第五个的取值个数为总数-前四数之和；
        }
        }
        }
        }
        }
        System.out.println("个数为"+count);
           }
    }
public int round(float num){
BigDecimal big = new BigDecimal(Float.toString(num));
BigDecimal big1 = new BigDecimal("1");
int rs = big.divide(big1,0,BigDecimal.ROUND_UP).intValue();
return rs;
}
public static void main(String[] args){
RankNumber r = new RankNumber();
int input_Number = 500;//取代500以内的不重复的5个整数和小于500;
r.test(input_Number);
}
}

Answer 25

虽然不够快,但是够通用: public static int comb( int num, int sum, int start, int end )
{
if( num == 1 ) {
if( sum >= start && sum <= end ) {
return sum - start + 1;
} else {
return 0;
}
}

int s = 0;

for( int i = start; i < end; i++ ) {
if( sum >= start ) {
s += comb( num - 1, sum - i, i + 1, end);
}
}
return s;
}本题的答案只要调用:comb( 5, 99, 1, 100 );

Answer 26

public static void method() {
int[] random = new int[10]; 
int i = 0;
do {
boolean find = false;
int num = (int) (Math.random() * 50) + 1; // 产生随机数不大于100
for (int index = 0; index < random.length; index++) {
if (random[index] == num) {
find = true; 
break;
}
}
if (find) { //如果已经存该数
continue;
}
random[i] = num;
i++;
} while (i < random.length);        

int sum = 0;
for (int j = 0; j < random.length / 2; j++) {
if(j==(random.length/2)-1){
sum = random[j - 1] + random[j];
System.out.println(sum);
}
else{
sum = random[j] + random[j+1];
System.out.println(sum);
}
}
}
public static void main(String[] args) {
method();
}

Answer 27

不好意思我错了。。
找了好久。。原来在这里
现在重新贴上去
请高人指点一下package test;import java.util.*;/**
 * 1-100中, 求:5个不同数的和小于100的不重复组合的个数.
 */
public class AlogRandom { /**
 * 获取两个不同数
 */
public static int[] method() { int[] random = new int[2]; boolean find = false; int i = 0; do {
int num = (int) (Math.random() * 99) + 1;
for (int j = 0; j < random.length; j++) {
if (num == random[i]) {
find = true;
break;
}
if (find) {
continue;
}
}
random[i] = num;
i++;
} while (i < random.length); return random;
} @SuppressWarnings("unchecked")
public static void GetRes() { List list = new ArrayList(); int[] sumList = new int[5]; int index = 0;

boolean find = false;

do {

int[] random = method();
for (int i = 0; i < sumList.length; i++) {
if (sumList[i] == (random[0] + random[1])) {
find = true;
break;
} 
if (find) {
continue;
}
}
int sum=random[0]+random[1];
if (sum >= 100) { // 如果结果大于等于100重新调用该方法
continue;
}
list.add(random[0]);
list.add(random[1]);
sumList[index] = (random[0] + random[1]);
index++;
} while (index < sumList.length);

for (int j = 0; j < list.size(); j++) {
System.out.println("产生100以内的数: 第" +(j+1)+"个"+ list.get(j));
}
System.out.println();
int x=0;
for (int k = 0; k < sumList.length; k++) {
System.out.println("第"+(++x)+"数加第"+(++x)+"数的和为: " + sumList[k]);
}
} public static void main(String[] args) {
GetRes();
}
}