面试算法题

Question

从1到100中取出10个不同的数，要求打印出所有可能的组合  请高手指教

Answer 1

曾经看到过,给你了
 public static string[] ToSingle(string Number)     //格式   01   02   03   04   05   06   07 
        {
            string[] words = Number.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
            StringBuilder singles = new StringBuilder();
            int Max = 1 << words.Length;
            int[] Mark = new int[Max];
            for (int i = 1; i < Max; i++)
                if ((Mark[i] = Mark[i >> 1] + (i & 1)) == 6)
                {
                    for (int k = 0; k < words.Length; k++)
                        if ((i & (1 << k)) != 0)
                            singles.Append(words[k] + "  ");
                    singles.Replace("  ", ";", singles.Length - 2, 2);
                }
            return singles.ToString().Split(';');
        }
        static void Main(string[] args)
        {
            string Number = "01   02   03   04   05   06   07";
            string[] singles = ToSingle(Number);
            foreach (string s in singles)
                Console.WriteLine(s);
            Console.Read();
        }

Answer 2

转帖一个.
-------------------------------------------------------------------------------------组合算法 
本程序的思路是开一个数组，其下标表示1到m个数，数组元素的值为1表示其下标 
代表的数被选中，为0则没选中。  
首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。  
然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为 
“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。  
当第一个“1”移动到数组的m-n的位置，即n个“1”全部移动到最右端时，就得 
到了最后一个组合。  
例如求5中选3的组合：  
1 1 1 0 0 //1,2,3  
1 1 0 1 0 //1,2,4  
1 0 1 1 0 //1,3,4  
0 1 1 1 0 //2,3,4  
1 1 0 0 1 //1,2,5  请访问：http://www.cnnic-qd.cn/it/index.html 
1 0 1 0 1 //1,3,5  
0 1 1 0 1 //2,3,5  
1 0 0 1 1 //1,4,5  
0 1 0 1 1 //2,4,5  
0 0 1 1 1 //3,4,5  程序如下：  #include "stdio.h"  
#include "time.h"  unsigned char number[100]; //最多求100个数的组合。  
unsigned int m,n;// 2<=m<=100,n<m  char tmpbuf[128];  
time_t ltime;  
struct tm *today;  void printtime(void) //打印当前时间的函数  
{  
time(<ime);  
today = localtime(<ime );  
strftime(tmpbuf,128,"%Y-%m-%d %H:%M:%S",today);  
printf("%s\n",tmpbuf);  
}  void inition() //初始化  
{  http://www.cnnic-qd.cn/it/index.html 
unsigned int i;  
for(i=0;i<n;i++)  
number[i]=1;  
}  void output() //输出组合结果  
{  
unsigned int i;  
for(i=0;i<m;i++)  
if(number[i])  
printf("%02d ",i+1);  
printf("\n");  
}  void main()  
{  
unsigned long count; //计数组合个数  
unsigned int i,j,k,l;  
bool findfirst,end,swap;  
end=false;  
printf("please input m:");  
scanf("%d",&m); //输入m  
printf("please input n:");  
scanf("%d",&n); //输入n  
printtime(); //打印开始时间  
inition(); //初始化  
//output(); //屏蔽掉结果输出以节约时间  
count=1;  
j=m;  
while(!end)  
{  
findfirst=false;  http://www.cnnic-qd.cn/it/index.htmlswap=false; //标志复位  
for(i=0;i<j;i++)  
{  
if(!findfirst && number[i])  
{  
k=i; //k记录下扫描到的第一个数  
findfirst=true; //设置标志  
}  
if(number[i] && !number[i+1]) //从左到右扫描第一个“10”组合  
{  
number[i]=0;  
number[i+1]=1;  
swap=true; //设置交换标志  
for(l=0;l<i-k;l++)  
number[l]=number[k+l];  
for(l=i-k;l<i;l++)  
number[l]=0; //交换后将之前的“1”全部移动到最左端  
if(k==i && i+1==m-n) //如果第一个“1”已经移动到了m-n的位置，说明 
这是最后一个组合了。  
end=true;  
}  
if(swap) //交换一次后就不用继续找“10”组合了  
break;  
}  
//output(); //屏蔽掉结果输出以节约时间  
count++; //组合数计数器递增1  
}  
printtime(); //打印结束时间  
http://www.cnnic-qd.cn/it/index.html
printf("total number of combination is: %d\n",count); //打印总的组合数 getchar();  
}  在vc5.0下编译通过.  
在我的p166 16M RAM机器上算30中选10 的组合，屏蔽掉结果输出花了33秒时间。 --------------------------------------------------------------- 全排列算法 从1到N，输出全排列，共N！条。 
分析：用N进制的方法吧。设一个N个单元的数组，对第一个单元做加一操作，满N进 
一。每加一次一就判断一下各位数组单元有无重复，有则再转回去做加一操作，没 
有则说明得到了一个排列方案。 
解法一：执行速度：10秒 
#include <stdio.h> 
#define n 5 
int a[n],b[n]; 
void swap(int m) 
{ 
int b1=b[m]; 
int b0=b1; 
while(a[b0]>=m){ 
b0--; 
if(b0<0)b0=n-1; 
} 
int temp=a[b0]; 
a[b0]=a[b1]; 
a[b1]=temp; 
int a0=a[b0]; 
int a1=a[b1]; 
http://www.cnnic-qd.cn/it/index.htmltemp=b[a0]; 
b[a0]=b[a1]; 
b[a1]=temp; 
} 
void output() 
{ 
for(int j=0;j<n;j++){ 
printf("%d ",a[j]); 
} 
printf("\n"); 
} 
void permute(int m) 
{ 
m--; 
for(int i=m;i>=0;i--){ 
permute(m); 
if(i>0){ 
swap(m); 
output(); 
} 
} 
} 
void main() 
{ 
for(int i=0;i<n;i++){ 
a[i]=b[i]=i; 
} 
output(); 
permute(n); 
} 解法二：5秒 
# include <stdio.h> 
# include <alloc.h> 
int N; 
main() 
{ 
int i,j,k,m,n,*l,*a,m2; 
scanf("%d",&N); 
if(N<3) 
{ 
puts("N太小!"); 
exit(1); 
} 
/* 开数组 */ 
l=malloc(N*sizeof(int)); 
a=malloc(N*sizeof(int)); 
/* 赋初值 */ 
for(i=0;i<N;i++) 
{ 
a[i]=0;l[i]=i+1; /* a[i]-1是第i个元素交换的次数 */ http://www.cnnic-qd.cn/it/index.html 
} 
m=2;put(l); 
do 
{ 
n=l[1];l[1]=l[0];l[0]=n;put(l); /* 头两个先换一下 */ 
/* 判断该换哪个了 */ 
while(a[m-2] == m) 
m++; 
if(m==N) break; 
/* 下面是整理过程，可能还有办法 */ 
n=m>>1; 
for(i=0,j=m-1;i<n;i++,j--) 
{ 
k=l[i]; 
l[i]=l[j]; 
l[j]=k; 
} /* 以上是从小到大重排，下面处理好了可能不必做，因为可以无序 
*/ 
m2=m-2; 
a[m2]++; 
/* 下面该把第j个和第m个交换 */ 
j=m-a[m2]; 
n=l[j];l[j]=l[m];l[m]=n; 
put(l); 
/* m以前的重排 */ 
for(i=0;i<m2;i++) 
a[i]=0; 
m=2; 
} while(1); 
} 
put(int *l) 
{ 
int i; 
for(i=0;i<N;i++) 
printf(" %2d",l[i]); 
putchar('\n'); 
} 

Answer 3

100*99*...*91,  about 100,000,000,000,000,000,000 combinations.suppose you can print 1 billion combinations in a second!you still need 100 billion seconds. That is about 3000 years!

Answer 4

在vc5.0下编译通过. 
在我的p166 16M RAM机器上算30中选10 的组合，屏蔽掉结果输出花了33秒时间。 
为什么在我的机器上10分钟呢？