1

请帮我解决这个任务：生成所有长度为 n 且设置了 k 位的二进制字符串。（需要写在 C 上）例如：

n=5
k=3
11100
00111
11010
01011
**01110
11001
10011
**01101
**10110
10101

** 无法生成这些排列

代码：

#include <stdio.h>
#define N 10
int main (void)
{
int mas[N]={0},kst,m,n1,z,a,b;
printf("\n\nVvedit` rozmirnist` masyvu: ");
scanf("%d",&kst);
printf("\n\nVvedit` kil`kist` odynyc`: ");
scanf("%d",&n1);
for(m=0;m1;m++)
   mas[m]=1;
for(m=0;m<kst;m++)
   printf("%d",mas[m]);
printf("\n");
for(m=0;m<n1;m++){
   for(z=0;z<(kst-1);z++)
     if((mas[z]==1) && (mas[z+1]==0)){
     a=mas[z];
     mas[z]=mas[z+1];
     mas[z+1]=a;
     for(b=0;b<kst;b++)
        printf("%d",mas[b]);
printf("\n");

      }
  }

return 0;
}
4

8 回答 8

2

这个问题我早就解决了！请在下面找到我的代码！我希望这会帮助你。

#include<stdio.h>

int NumberOfBitsSet(int number)
{
    int BitsSet = 0;

    while(number != 0)
    {

        if(number & 0x01)
        {
            BitsSet++;
        }
        number = number >> 1;
    }

    return BitsSet;
}

void PrintNumberInBinary(int number, int NumBits)
{
    int val;
    val = 1 << NumBits; // here val is the maximum possible number of N bits with only MSB set

    while(val != 0)
    {
        if(number & val)
        {
            printf("1");
        }
        else
        {
            printf("0");
        }

        val = val >> 1;
    }
}

int main()
{
    int n,k,i;
    int max,min;
    printf("enter total number of bits and number of bits to be set:\n");
    scanf("%d %d", &n, &k);

    min = ((1 << k) - 1); //min possible values with k bits set
    max = (min << (n-k)); //max possible value with k bits set!
    //printf("%d %d", min, max);
    for(i=0; i<= max; i++)
    {
        if(!(i<min))
        {
            if(NumberOfBitsSet(i) == k)
            {
                PrintNumberInBinary(i, (n-1));
                printf("\n");
            }
        }
    }

    return 0;
}
于 2013-10-29T10:38:02.880 回答
1

你的代码一团糟；）

说真的：用代码解决任务的第一条规则是编写干净的代码，使用合理的变量命名等。

对于像这样的任务，我建议使用这个。

现在到您的示例代码：它不会编译并且很难阅读您正在尝试做的事情。格式化并带有一些注释：

#include <stdio.h>

#define N 10

int main(void)
{
        int mas[N] = {0};
        int kst, m, n1, z, a, b;

        /* Read width ? */
        printf("\n\nVvedit` rozmirnist` masyvu: ");
        scanf("%d", &kst);
        /* Read number of bit's set? */
        printf("\n\nVvedit` kil`kist` odynyc`: ");
        scanf("%d", &n1);

        /* m1 is not defined, thus the loop give no meaning. 
         * Guess you are trying to set "bits" integers to 1.
         */
        for (m = 0; m1; m++)
                mas[m] = 1;

        /* This should be in a function as 1. You do it more then once, and
         * 2. It makes the code much cleaner and easy to maintain.
         */
        for (m = 0; m < kst; m++)
                printf("%d", mas[m]);
        printf("\n");

        for (m = 0; m < n1; m++) {
                for (z = 0; z < (kst - 1); z++) {
                        if ((mas[z] == 1) && (mas[z + 1] == 0)) {
                                a = mas[z];            /* Same as a = 1; */
                                mas[z] = mas[z + 1];   /* Same as mas[z] = 0; */
                                mas[z + 1] = a;        /* Same as mas[z + 1] = 1; */

                                /* Put this into a function. */
                                for (b = 0; b < kst; b++)
                                        printf("%d", mas[b]);
                                printf("\n");
                        }
                }
        }

        return 0;
}

printf当一个人不确定发生了什么时，广泛使用是一种宝贵的工具。这不是一个解决方案，（它基本上和你的帖子一样，但是分开了），而是一个可能更容易使用的示例。我还使用 char 数组作为 C 字符串而不是整数数组。在这种情况下更容易使用。

如果您想使用整数数组，我建议您添加一个print_perm(int *perm, int width)辅助函数以将其从主代码中取出。

#include <stdio.h>

#define MAX_WIDTH 10

int get_spec(int *width, int *bits)
{
        fprintf(stderr, "Enter width    (max %-2d): ", MAX_WIDTH);
        scanf("%d", width);

        if (*width > MAX_WIDTH) {
                fprintf(stderr, "Bad input: %d > %d\n", *width, MAX_WIDTH);
                return 1;
        }

        fprintf(stderr, "Enter set bits (max %-2d): ", *width);
        scanf("%d", bits);

        if (*bits > MAX_WIDTH) {
                fprintf(stderr, "Bad input: %d > %d\n", *bits, MAX_WIDTH);
                return 1;
        }

        return 0;
}

void permutate(int width, int bits)
{
        char perm[MAX_WIDTH + 1];
        int i, j;

        /* Set "bits"  */
        for (i = 0; i < width; ++i)
                perm[i] = i < bits ? '1' : '0';

        /* Terminate C string */
        perm[i] = '\0';

        fprintf(stderr, "\nPermutations:\n");
        printf("%s\n", perm);

        for (i = 0; i < bits; ++i) {
                /* Debug print current perm and outer iteration number */
                printf("%*s LOOP(%d)   %s\n", 
                        width, "", i, perm
                );

                for (j = 0; j < (width - 1); ++j) {
                        if (perm[j] == '1' && perm[j + 1] == '0') {
                                perm[j] = '0';
                                perm[j + 1] = '1';

                                printf("%s j=%d print\n", 
                                        perm, j
                                );
                        } else {
                                /* Debug print */
                                printf("%*s j=%d skip  %s\n", 
                                        width, "", j, perm
                                );
                        }
                }
        }
}

int main(void)
{
        int width, bits;

        if (get_spec(&width, &bits))
                return 1;

        permutate(width, bits);

        return 0;
}
于 2013-10-29T13:18:55.080 回答
0

尝试这个

A[n-1]=0;
func(n-1);
A[n-1]=1;
func(n-1);
于 2014-04-19T05:32:54.040 回答
0 
//Think simple people but please bear with me i love java

//Assume array A is globally defined

void Binary(int n)
{
    if(n<1)
    {
        System.out.println(A);
    }
    else
    {
        A[n-1]=0;
        Binary(n-1);
        A[n-1]=1;
        Binary(n-1);
    }
}
于 2014-08-14T19:08:26.663 回答
0

如果您想在不执行“迭代和检查”的情况下唯一地列出所有排列，您可以执行以下操作：

# Move peg x up m using s
# x is negative
# m is positive
def move(x, m, s):
    for i in range(1, m+1):
        s2 = list(s)

        s2[x] = 0
        s2[x - i] = 1

        print(s2)

        if x + 1 < 0:
            move(x+1, i, s2)

# Print all unique permutations of 
# n bits with k ones (and n-k zeros)
def uniqPerms(n, k):
    s = [0 for _ in range(n-k)] + [1 for _ in range(k)]

    print(s)
    move(-k, n-k, s)

if __name__ == '__main__':
    from sys import argv
    uniqPerms(int(argv[1]), int(argv[2]))

这个想法是你递归地增加 1，这样每个动作都会产生一个唯一的列表（因为 1 现在是以前没有的地方）。

你说它必须在C中：

#include <stdio.h>
#include <stdlib.h>

enum { n = 8 };

struct string
{
    char str[n + 1];
};

void move(int x, int m, string s)
{
    for (int i = 0; i <= m; ++i)
    {
        string s2 = s;
        s2.str[n + x] = '0';
        s2.str[n + x - i] = '1';
        printf("%s\n", s2.str);

        if (x + 1 < 0)
            move(x + 1, i, s2);
    }
}

void uniqPerms(int k)
{
    string s;
    for (int i = 0; i < n - k; ++i)
        s.str[i] = '0';
    for (int i = n - k; i < n; ++i)
        s.str[i] = '1';
    s.str[n] = '\0';

    printf("%s\n", s.str);
    move(-k, n - k, s);
}

int main(int argc, char *argv[])
{
    uniqPerms(atoi(argv[1]));
    return 0;
}
于 2014-03-02T22:52:35.667 回答
0

这是递归解决方案

#include <iostream>
#include <vector>

using namespace std;


char v[4];
int count = 0;

void printString(){
    int i;
    for(i = 0; i < 4; i++){
        cout << v[i] << "  ";
    }
    cout <<count <<  endl;
 }


void binary(int n){
if(n < 0){
    if(count == 2)
        printString();
}
else{
    v[n] = '0';
    binary(n - 1);
    v[n] = '1';
    count++;
    binary(n-1);
    count--;
}
}



int main(){
binary(3);
return 0;
 }
于 2016-12-01T12:24:52.510 回答
-1 
#include<stdio.h>
int main(){
int n,k,i,j,a[50];
//lets suppose maximum size is 50
printf("Enter the value for n");
scanf("%d",&n);
printf("Enter the value for k");
scanf("%d",&k);
//create an initial bitstring of k 1's and n-k 0's;
for(i=0;i<n;i++){
if(k>0)    
   a[i]=1;
else
   a[i]=0;
k--;
}
for(i=0;i<n;i++){
if(a[i]==1){
for(j=0;j<n;j++){
if(j!=i&&a[j]==0){
a[j]=1;a[i]=0;
for(k=0;k<n;k++){printf("%d\n",a[k]);}
a[i]=1; a[j]=0;
}}}}
return 0;
}
于 2013-10-29T10:13:08.723 回答
-1

**如果复杂性无关紧要，您可以使用以下在 java 中完成的代码。它将在 o(2^n) 中提供所需的输出。在这里，我找到了大小为 n 的数组中给定 n 位的 0 和 1 的所有组合。如果设置了 K 位，我已经计算了 1 的数量呈现等于 k ​​使用 countBits() 函数。如果我打印了该数组。

public class GenerateAllStringOfNBitsWithKBitsSet {
     public static  int a[] ={0,0,0,0,0};
     static int k=3;
     public static boolean countBits(){
        int  y=0;
         for(int i=0;i<a.length;i++)   
           y += a[i] &  1 ;

         if(y==k)
             return true;
         return false;
       }
        public static void gen(int n)
        {
            if(n<1)
            {
                if(countBits())
                System.out.println(Arrays.toString(a));

            }
            else
            { 
                 a[n-1]=0;
                 gen(n-1);
                 a[n-1]=1;
                 gen(n-1);
            }
        }
        public static void main(String[] args) {


            GenerateAllStringOfNBitsWithKBitsSet.gen(a.length);
        }

}
于 2015-12-28T19:50:40.693 回答