每日一算法:m元素中取n个元素(高效算法)

缺乏、安全感 2022-09-18 06:57 139阅读 0赞

五个数种取三个  
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  
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  
思路，如上所示，找到第一个 1 0 分界点。将分界点前面的1的个数从第一个位置开始往后排  
排完后再将所排位置与分界点的位置之间排0。如此循环即可。

#include <stdio.h>
    
    void fulledition (int m,int n)
    {//m个数中取n个
    	int t[1000];
    	int i,a,sum,b;
    	for (i=1;i<=n;i++)
    	{//1...n全部初始化为1
    		t[i]=1;
    	}
    	for (i=n+1;i<=m;i++)
    	{//n+1...m全部初始化为0
    		t[i]=0;
    	}      //初始化t[i]的值
    	for(i=1;i<=m;i++)
    	{//先打印1...n
    		if (t[i]==1)
    
    	    printf("%d ",i);
    	}
    	printf("\n");
    
    
    	for(i=1;i<=m;i++)
    	{
    		if(t[i]==1&&t[i+1]==0)
    		{//查找第一个分界点，将这个分界点0变为1,1变为0
    			sum=0;
    			for(a=1;a<i;a++)
    			{//计算分界点前面1的个数，然后从前往后置1
    				sum=sum+t[a];
    			}
    			t[i+1]=1;
    			t[i]=0;
    			for(b=1;b<=sum;b++)
    			{//从1开始置1
    				t[b]=1;
    			}
    			for(b=sum+1;b<i;b++)
    			{//从sum+1开始置0
    				t[b]=0;
    			}
    			for(i=1;i<=m;i++)
    			{//打印t[i]设置为1的i值
    				if (t[i]==1)
    				{
    					printf("%d ",i);
    				}
    			}
    			printf("\n");
    			i=0;//不断的从第一个开始寻找
    		}	
    	} 
    }
    
    
    
    int main ()
    {  
    	int n,m;
    	printf("输入M:");
    	scanf("%d",&m);
    	printf("输入N:");
    	scanf("%d",&n);
    	fulledition(m,n);
    	return 0;
    }