c – 找到将零插入位模式的所有方法

概述出于某种原因,我一直在努力解决这个问题.我有15位代表一个数字.这些位必须与模式匹配.模式以比特开始的方式定义：它们处于该模式的最正确表示.所以说模式是1 4 1.这些位将是： 000000010111101 因此,一般规则是,取模式中的每个数字,创建多个位(在这种情况下为1,4或1),然后至少有一个空格将它们分开.所以,如果它是1 2 6 1(它将是随机的)： 001011011111101 从 出于某种原因,我一直在努力解决这个问题.我有15位代表一个数字.这些位必须与模式匹配.模式以比特开始的方式定义：它们处于该模式的最正确表示.所以说模式是1 4 1.这些位将是：

000000010111101

因此,一般规则是,取模式中的每个数字,创建多个位(在这种情况下为1,4或1),然后至少有一个空格将它们分开.所以,如果它是1 2 6 1(它将是随机的)：

001011011111101

从刷新版本开始,我想生成满足该模式的每个可能的数字.位数将存储在变量中.因此,对于一个简单的情况,假设它是5位,初始位模式是：00101.我想生成：

00101
01001
01010
10001
10010
10100

我想在Objective-C中这样做,但任何类似C的东西都没问题.我似乎无法想出一个很好的递归算法.在上面的例子中它是有道理的,但是当我开始进入12431并且必须跟踪它所发生的一切时.

解决方法 在 @Mark Byers’s和 Moron’s答案的基础上建立您的任务可以重新制定如下：

枚举将K零点放入N个位置的所有方法(参见combinations with repetition和Stars and bars).

示例：对于15位和1 2 6 1模式,存在N = 5个位置(数字之前/之后以及1之间)以使K = 2个零(正确数字的前导零数).方式的数量是binomial(N K-1,K),即二项式(5 2-1,2)= 15.

以下代码中的关键功能是next_combination_counts()和comb2number().

完整的C程序

#include <assert.h>#include <stdbool.h>#include <stdio.h>#define SIZE(arr) (sizeof(arr)/sizeof(*(arr)))#define PRInumber "u"typedef unsigned number_t;// swap values pointed to by the pointerstatic voIDiter_swap(int* ia,int* ib) {  int t = *ia;  *ia = *ib;  *ib = t;}// see boost::next_combinations_counts()// http://photon.poly.edu/~hbr/boost/combinations.HTML// http://photon.poly.edu/~hbr/boost/combination.hppstatic bool next_combination_counts(int* first,int* last) {  /*0 0 2 0 1 1 0 2 0 1 0 1 1 1 0 2 0 0    */    int* current = last;    while (current != first && *(--current) == 0) {    }    if (current == first) {        if (first != last && *first != 0)            iter_swap(--last,first);        return false;    }    --(*current);    iter_swap(--last,current);    ++(*(--current));    return true;}// convert combination and pattern to corresponding number// example: comb=[2,0] pattern=[1,1] => num=5 (101 binary)static number_t comb2number(int comb[],int comb_size,int pattern[],int pattern_size) {  if (pattern_size == 0)    return 0;  assert(pattern_size > 0);  assert(comb_size > pattern_size);  // 111 -> 1000 - 1 -> 2**3 - 1 -> (1 << 3) - 1  // 111 << 2 -> 11100  number_t num = ((1 << pattern[pattern_size-1]) - 1) << comb[pattern_size];    int len = pattern[pattern_size-1] + comb[pattern_size];  for (int i = pattern_size - 1; i--> 0; ) {    num += ((1 << pattern[i]) - 1) << (comb[i+1] + 1 + len);    len += pattern[i] + comb[i+1] + 1;  }    return num;}// print binary representation of numberstatic voID print_binary(number_t number) {  if (number > 0) {    print_binary(number >> 1);    printf("%d",number & 1);  }}// print arraystatic voIDprinta(int arr[],int size,const char* suffix) {  printf("%s","{");  for (int i = 0; i < (size - 1); ++i)    printf("%d,",arr[i]);  if (size > 0)    printf("%d",arr[size - 1]);  printf("}%s",suffix);}static voID fill0(int* first,int* last) {  for ( ; first != last; ++first)    *first = 0;}// generate {0,...,nzeros} combinationstatic voIDinit_comb(int comb[],int nzeros) {  fill0(comb,comb + comb_size);  comb[comb_size-1] = nzeros;}static intsum(int* first,int* last) {  int s = 0;  for ( ; first != last; ++first)    s += *first;  return s;}// calculated max wIDth required to print number (in PRInumber format)static int maxwIDth(int comb[],int pattern_size) {  int initial_comb[comb_size];  int nzeros = sum(comb,comb + comb_size);  init_comb(initial_comb,comb_size,nzeros);  return snprintf(NulL,"%" PRInumber,comb2number(initial_comb,pattern,pattern_size)); }static voID process(int comb[],int pattern_size) {  // print combination and pattern  printa(comb," ");  printa(pattern,pattern_size," ");  // print corresponding number  for (int i = 0; i < comb[0]; ++i)    printf("%s","0");  number_t number = comb2number(comb,pattern_size);  print_binary(number);  const int wIDth = maxwIDth(comb,pattern_size);  printf(" %*" PRInumber "\n",wIDth,number);}// reverse the arraystatic voID reverse(int a[],int n) {  for (int i = 0,j = n - 1; i < j; ++i,--j)     iter_swap(a + i,a + j);  }// convert number to pattern// 101101111110100 -> 1,2,6,1static int number2pattern(number_t num,int nbits,int comb[]) {  // SIZE(pattern) >= nbits  // SIZE(comb) >= nbits + 1  fill0(pattern,pattern + nbits);  fill0(comb,comb + nbits + 1);  int i = 0;  int pos = 0;  for (; i < nbits && num; ++i) {    // skip trailing zeros    for ( ; num && !(num & 1); num >>= 1,++pos)      ++comb[i];    // count number of 1s    for ( ; num & 1; num >>=1,++pos)       ++pattern[i];  }  assert(i == nbits || pattern[i] == 0);    const int pattern_size = i;    // skip comb[0]  for (int j = 1; j < pattern_size; ++j) --comb[j];  comb[pattern_size] = nbits - pos;  reverse(pattern,pattern_size);  reverse(comb,pattern_size+1);  return pattern_size;}int main(voID) {  number_t num = 11769;   const int nbits = 15;  // clear hi bits (required for `comb2number() != num` relation)  if (nbits < 8*sizeof(number_t))    num &=  ((number_t)1 << nbits) - 1;  else    assert(nbits == 8*sizeof(number_t));  // `pattern` defines how 1s are distributed in the number  int pattern[nbits];  // `comb` defines how zeros are distributed   int comb[nbits+1];  const int pattern_size = number2pattern(num,nbits,comb);  const int comb_size = pattern_size + 1;  // check consistency  // . find number of leading zeros in a flush-right version  int nzeros = nbits;  for (int i = 0; i < (pattern_size - 1); ++i)    nzeros -= pattern[i] + 1;  assert(pattern_size > 0);  nzeros -= pattern[pattern_size - 1];  assert(nzeros>=0);  // . the same but using combination  int nzeros_comb = sum(comb,comb + comb_size);  assert(nzeros_comb == nzeros);  // enumerate all combinations   printf("Combination Pattern Binary Decimal\n");  assert(comb2number(comb,pattern_size) == num);  process(comb,pattern_size); // process `num`  // . until flush-left number   while(next_combination_counts(comb,comb + comb_size))    process(comb,pattern_size);  // . until `num` number is encounterd    while (comb2number(comb,pattern_size) != num) {    process(comb,pattern_size);    (voID)next_combination_counts(comb,comb + comb_size);  }  return 0;}

输出：

Combination Pattern Binary Decimal{1,1,0} {1,1} 010110111111001 11769{1,1} 010110011111101 11517{1,1} 010011011111101  9981{2,1} 001011011111101  5885{0,2} {1,1} 101101111110100 23540{0,1} {1,1} 101101111110010 23538{0,1} 101101111110001 23537{0,1} 101100111111010 23034{0,1} 101100111111001 23033{0,1} 101100011111101 22781{0,1} 100110111111010 19962{0,1} 100110111111001 19961{0,1} 100110011111101 19709{0,1} 100011011111101 18173{1,1} 010110111111010 11770

总结

以上是内存溢出为你收集整理的c – 找到将零插入位模式的所有方法全部内容，希望文章能够帮你解决c – 找到将零插入位模式的所有方法所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。