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

あなたのコードはめちゃくちゃです;）

真剣に：コードでタスクを解決するときの最初のルールは、きれいなコードを書くこと、賢明な変数命名などを使用することです.

このようなタスクについては、 this を使用することをお勧めします。

次に、サンプル コードを見てみましょう。これはコンパイルされず、何をしようとしているのかを読み取るのは困難です。フォーマット済みでコメントあり:

#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

「反復とチェック」を行わずにすべての順列を一意にリストしたい場合は、次のようにすることができます。

# 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 に答える
-1

**複雑さが問題にならない場合は、Java で行われる次のコードを使用できます。これにより、o(2^n) で目的の出力が得られます。ここでは、サイズ n の配列で指定された n ビットの 0 と 1 のすべての組み合わせを見つけました。K ビットが設定されている場合、1 の数を数えました。 present は countBits() funtion.if を使用して k に等しいので、その配列を出力しました。

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 に答える