729 - The Hamming Distance Problem

[cpp] view plaincopyprint?
描述：和前面的几道水题一样，还是两种代码，使用库函数的话耗时比较少一点，用刘汝佳的生成可重集排列的方法耗时多，没什么难度 
 
 
 
代码一： 
 
 
 
#include <iostream> 
#include <cstdio> 
#include <cstring> 
#include <algorithm> 
using namespace std; 
int main() 
{ 
    //freopen("a.txt","r",stdin); 
    char s[20]; 
    int n,len,m; 
    scanf("%d",&n); 
    while(n--) 
    { 
        scanf("%d%d",&len,&m); 
        memset(s,0,sizeof(s)); 
        for(int i=0;i<len-m;i++) s[i]='0'; 
        for(int i=len-m;i<len;i++) s[i]='1'; 
        do 
        { 
            printf("%s/n",s); 
        }while(next_permutation(s,s+len)); 
        if(n) printf("/n"); 
    } 
    return 0; 
} 
 
 
 
代码二： 
 
 
 
#include <iostream> 
#include <cstdio> 
#include <cstring> 
#include <algorithm> 
using namespace std; 
void print_permutation(char *s,char *str,int len ,int cur) 
{ 
    if(cur==len) printf("%s/n",str); 
    else for(int i=0;i<len;i++) 
    if(!i||s[i]!=s[i-1]) 
    { 
        int c1(0),c2(0); 
        for(int j=0;j<len;j++) if(s[i]==s[j]) c1++; 
        for(int j=0;j<cur;j++) if(s[i]==str[j]) c2++; 
        if(c2<c1) 
        { 
            str[cur]=s[i]; 
            print_permutation(s,str,len,cur+1); 
        } 
    } 
} 
int main() 
{ 
    //freopen("a.txt","r",stdin); 
    char s[20],str[20]; 
    int n,len,m; 
    scanf("%d",&n); 
    while(n--) 
    { 
        scanf("%d%d",&len,&m); 
        memset(s,0,sizeof(s)); 
        for(int i=0;i<len-m;i++) s[i]='0'; 
        for(int i=len-m;i<len;i++) s[i]='1'; 
        memset(str,0,sizeof(str)); 
        print_permutation(s,str,len,0); 
        if(n) printf("/n"); 
    } 
    return 0; 
}