Знайсці лік двайковых лікаў з пэўнымі абмежаваннямі

Гэта больш, чым галаваломкі праблемы кадавання. Мне трэба знайсці, колькі двайковых лікаў можа быць згенераваныя, якія задавальняюць пэўныя абмежаванні. ўваходы

(integer) Len - Number of digits in the binary number
(integer) x
(integer) y

Двайковае лік павінна быць такім, каб прымаць любы х суседнія лічбы з двайковага ліку павінна ўтрымліваць, па меншай меры, у 1-х.

Напрыклад -

<�Р> Len = 6, х = 3, у = 2 </р>      <�Р> 0 1 1 0 1 1 - даўжыня 6, прымае любыя 3 сумежных лічбаў ад гэтага і   будзе 2 адзінак </р>

У мяне быў C# кадавання пытанне, пастаўлены мне ў інтэрв'ю, і я не магу зразумець, любы алгарытм для вырашэння гэтага. Не маю патрэбу ў кодзе (хоць гэта вітаецца), любы від дапамогі, паказальнікі ацэненыя

16
@AlexFilipovici 000101 не зьяўляецца сапраўдным лікам, «любыя суседнія х лічбы ад двайковага ліку павінны ўтрымліваць, па меншай меры, у 1», і 000 ня робіць.
дададзена аўтар Francesco De Lisi, крыніца
Што даўжыня згенераваных лікаў? Павінна быць = Len або <= Len? Гэта не ясна.
дададзена аўтар Francesco De Lisi, крыніца
@AlexFilipovici Я думаю, вы павінны разгледзець ўсю паслядоўнасць, а не яго дзесятковы ўяўленне. Гэта паслядоўнасць біт. Можа быць, гэтае пытанне можа быць «Колькі двайковых лікаў даўжыні = Len могуць быць згенераваныя ...»
дададзена аўтар Francesco De Lisi, крыніца
<�Код> 011011 мае даўжыню 6 ці 5? Калі вы хочаце стварыць алгарытм для задачы вам неабходна ачысціць, калі, скажам, 000101 з'яўляецца сапраўдным лік, знойдзенае па алгарытме, які на самай справе 101 (менш чым 111111 , самая вялікая колькасць, улічваючы Len зменная), і гэта таксама задавальняе (х, у) стан. У прынцыпе, вы павінны ведаць, калі вы глядзіце ў 000000 - 111111 інтэрвал або проста 100000 - 111111 .
дададзена аўтар Alex Filipovici, крыніца
@FrancescoDeLisi, 101 менш, чым найбольшая колькасць генераванага кода <> Len = 6 зменную (г.зн. 111111 ). Калі палічыць алгарытм толькі паміж лікамі, якія маюць двайковае ўяўленне роўна 6 лічбаў або паміж усімі лікамі, якія менш або роўна <�кодам> 111111 ? У апошнім выпадку, Len будзе толькі 3 для 101 .
дададзена аўтар Alex Filipovici, крыніца
@FrancescoDeLisi = Len
дададзена аўтар Arun, крыніца

11 адказы

Гэтая праблема можа быць вырашана з дапамогай дынамічнага праграмавання. Асноўная ідэя заключаецца ў групу двайковых лікаў у адпаведнасці з апошнім X-1 біт, а даўжынёй кожнага двайковага ліку. Калі даданне паслядоўнасці бітаў на адзін нумар дае лік, якое задавальняе абмежавання, а затым дадаючы тую ж паслядоўнасць бітаў на любы лік у адных і тых жа вынікаў у групе лік, якое задавальняе абмежаванне таксама.

Так, напрыклад, х = 4, у = 2. Абодва 01011 і 10011 маюць тыя ж самыя апошнія 3 біта (011). Даданне ад 0 да кожнага з іх, у выніку чаго 010.110 і 100.110, і задавальняе абмежаванне.

Вось псеўда-код:

mask = (1<<(x-1)) - 1
count[0][0] = 1
for(i = 0; i < Len-1; ++i) {
    for(j = 0; j < 1<< 1<<(x-1); ++j) {
        if(i=y)
            count[i+1][(j*2+1)&mask] += count[i][j];
        if(i=y)
            count[i+1][(j*2)&mask] += count[i][j];
    }
}
answer = 0
for(j = 0; j < 1<< 1<<(x-1); ++j)
    answer += count[Len][j];

This algorithm assumes that Len >= x. The time complexity is O(Len*2^x).

<�Моцны> Змяніць

<�Код> count1Bit (к) функцыя падлічвае лік 1 у двайковым прадстаўленні J .

Толькі на ўваход гэтага алгарытму Лён, х і ў . Яна пачынаецца з пустой бінарнай радкі [даўжыня 0, група 0] , і итеративно спрабуе не дадаваць 0 і 1, пакуль даўжыня роўная Len. Яна таксама робіць групоўку і падлік колькасці двайковых радкоў, якія задавальняюць 1-бітае абмежаванне ў кожнай групе. Выхад гэтага алгарытму адказ , які з'яўляецца лікам двайковых радкоў (лікаў), якая адпавядае абмежаванняў.

Для двайковай радка ў групе [даўжыня я, гурт J] , даданне ад 0 да гэта прыводзіць да двайковай радка ў групе [даўжыня + 1, група (J * 2)% (2 (х-1))] ; даданне 1 да гэта прыводзіць да двайковай радка ў групе [даўжыні I + 1, група (J * 2 + 1),% (2 ^ (х-1))] .

Хай падлік [I, J] быць лік двайковых радкоў у групе [даўжыня я, гурт J] задавальняе 1-бітнае абмежаванне. Калі існуе, па меншай меры, у 1 у двайковым прадстаўленні J * 2 , а затым дадання 0 да кожнага з іх падлік [I, J] двайковыя радкі дае двойкавую радок у групе [даўжыня + 1, група (J * 2)% (2 ^ (х-1))] які таксама задавальняе 1-бітнае абмежаванне. Такім чынам, мы можам дадаць кол [I, J] у падлік [I + 1, (J * 2)% (2 ^ (х-1))] . Выпадак дадання 1 аналагічна.

The condition i in the above algorithm is to keep the binary strings growing when length is less than x-1.

2
дададзена
Ці можаце вы забяспечыць рэалізацыю вашых у алгарытме мове, які вы палічыце патрэбным ... Як @Arun я паспрабаваў яго код (у C, проста скапіяваць і ўставіць дадаўшы некаторыя ) не дало ніякіх вынікаў.
дададзена аўтар Ring Ø, крыніца
@ CS.Ferng Таму складанасць алгарытму з'яўляецца экспаненцыяльнай адносна у?
дададзена аўтар ElKamina, крыніца
Я думаю, што трэба быць геніем матэматыкі, каб зразумець гэта рашэнне. Я спрабую код, каб гэта праверыць выхад, але я затрымаўся ў другой апошняй радку «для (J = 0, J <1 << я && J <1 << (х-1); ++ J) "Што такое значэнне я '?
дададзена аўтар Arun, крыніца
Ваша рашэнне патрабуе набору двайковых лікаў у якасці ўваходных дадзеных, у той час як патрабаванне для падліку або генерацыі, а затым разлічваць двайковыя лікі, якія задавальняюць крытэрам
дададзена аўтар Arun, крыніца
@Arun я гэта індэкс вонкавага для цыклу, што азначае даўжыню двайковай радка, разгледжанай у гэтай ітэрацыі. Калі двайковая радок мае толькі я біты, яго нумар групы (апошнія X-1 біт, ці ўсё біты I, калі г <�х-1) не можа быць больш, чым 2 ^ я. Вось чаму "J <1 << я".
дададзена аўтар CS.Ferng, крыніца
@ElKamina Складанасць з'яўляецца экспаненцыяльнай па х. ў толькі парог і не ўплывае на складанасць.
дададзена аўтар CS.Ferng, крыніца
@Arun Не, уваход гэтага алгарытму Len, х і ў толькі. Адрэдагаваны для больш падрабязнага тлумачэння пра алгарытм.
дададзена аўтар CS.Ferng, крыніца

Выкарыстоўваючы прыклад LEN = 6, X = 3 і Y = 2 ...

Пабудаваць вычарпальны генератар бітаў для шаблону Х біт. Просты двайковы лічыльнік можа зрабіць гэта. Напрыклад, калі Х = 3 то лічыльнік ад 0 да 7 будзе генераваць ўсе магчымыя камбінацыі бітаў даўжыні 3.

Мадэлі з'яўляюцца:

000
001
010
011
100
101
110
111

Праверце патрабаванне сумежна, як будуюцца малюнкі. Адхіліць любыя ўзоры, якія не адпавядаюць крытэрам. У асноўным гэта зводзіцца да адмовы любы ўзор, які змяшчае менш чым 2 «1» біт (Y = 2). Спіс падразае ўніз:

011
101
110
111

Для кожнага члена абрэжа спіс, дадайце "1" біт і пераправяраць першыя X біт. Трымаеце новую мадэль, калі яна праходзіць сумежна тэст. Зрабіце тое ж самае з "0" біт. Напрыклад, гэты крок працягваецца, як:

1011  <== Keep
1101  <== Keep
1110  <== Keep
1111  <== Keep
0011  <== Reject
0101  <== Reject
0110  <== Keep
0111  <== Keep

Які пакідае:

1011
1101
1110
1111
0110
0111

Цяпер паспрабуйце гэты працэс да таго часу, абразаюць набор пусты або даўжыні члены становяцца LEN бітаў даўжынёй. У рэшце рэшт толькі мадэлі застаюцца наступныя:

111011
111101
111110
111111
110110
110111
101101
101110
101111
011011
011101
011110
011111

Колькасць іх, і вы зрабілі.

Звярніце ўвагу, што вам трэба толькі, каб праверыць першыя X біты на кожнай ітэрацыі, паколькі ўсе наступныя мадэлі былі правераныя ў папярэдніх кроках.

1
дададзена
@Patashu фіксуецца, каб прыняць/адхіліць мадэлі, заснаваныя на тым, па меншай меры, Y устаноўленыя біты.
дададзена аўтар NealB, крыніца
@Arun Даўжыня менш праблем, чым розніца паміж X і Y. Калі Y = 0 мноства адказаў змяшчае 2 ^ шаблоны Len, таму што ўсе разлічваць бітаў камбінацыі (не мае значэння, што Х ўяўляе сабой у гэтай кропцы). Калі Y = X толькі адзін шаблон, якія змяшчаюць біты ўсіх «1» ў наборы адказаў. Рашэнні, дзе Y з'яўляецца вялікім у параўнанні з X хутка знайшоў з-за «чарнасліву, як вы ідзяце стратэгіі», але атрымаць экспанентна павольней/больш, а Y памяншаецца адносна X. Такім чынам, гэты алгарытм мае O (2 ^ Len) найгоршае прастору і патрабаванне часу, але становіцца нашмат лепш, так як Y павялічваецца ў адносінах да X.
дададзена аўтар NealB, крыніца
@Arun Узгоднена. Гэта фундаментальная праблема любой генерацыі і алгарытм тэсту, дзе некаторыя ўваходы прыводзяць да экспанентным памерах набору. Проста пералік магчымых рашэнняў, дзе Len = 100, X = 10 і Y << Х будзе праблематычныя, хутчэй за ўсё, працуе ў трыльёны. Адзіны разумны падыход у гэтых умовах з'яўляецца прамым матэматычным рашэннем, як была зроблена ў адказ па Mikeb.
дададзена аўтар NealB, крыніца
Я думаю, вы зразумелі пытанне, вы павінны мець па крайняй меры, у бітаў ня ТОЧНО Y біт
дададзена аўтар Patashu, крыніца
Выглядае добра цяпер, +1
дададзена аўтар Patashu, крыніца
Ну з-за адсутнасці лепшага рашэння я пазначыў гэта як правільны адказ
дададзена аўтар Arun, крыніца
На жаль, я меў на ўвазе даўжыня = 100 і х = 10, таму што тады вы б выклікалі вызначаны лік двайковых лікаў з 10 лічбаў, а затым вы павінны завесы праз усе з іх, пакуль не дасягне 100 лічбаў (даданне 90 больш 0 'і/або 1-х), і гэта займае занадта шмат часу
дададзена аўтар Arun, крыніца
Гэта па аналогіі рашэння я даў, але калі даўжыня = 10, то гэта займае занадта шмат часу.
дададзена аўтар Arun, крыніца

Улічваючы, што ўваходныя значэння з'яўляюцца зменнымі і хацелі б бачыць фактычны выхад, я выкарыстаў рэкурсіўны алгарытм, каб вызначыць усе камбінацыі 0 і 1 для зададзенай даўжыні:

    private static void BinaryNumberWithOnes(int n, int dump, int ones, string s = "")
    {
        if (n == 0)
        {
            if (BinaryWithoutDumpCountContainsnumberOfOnes(s, dump,ones))
                Console.WriteLine(s);
            return;
        }
        BinaryNumberWithOnes(n - 1, dump, ones, s + "0");
        BinaryNumberWithOnes(n - 1, dump, ones, s + "1");
    }

і BinaryWithoutDumpCountContainsnumberOfOnes , каб вызначыць, ці з'яўляецца двайковае лік адпавядае крытэрам

private static bool BinaryWithoutDumpCountContainsnumberOfOnes(string binaryNumber, int dump, int ones)
    {
        int current = 0;
        int count = binaryNumber.Length;
        while(current +dump < count)
        {
            var fail = binaryNumber.Remove(current, dump).Replace("0", "").Length < ones;
            if (fail)
            {
                return false;
            }
            current++;
        }

        return true;
    }

Выклік BinaryNumberWithOnes (6, 3, 2) будзе выводзіць ўсе двайковыя лікі, якія адпавядаюць

010011
011011
011111
100011
100101
100111
101011
101101
101111
110011
110101
110110
110111
111011
111101
111110
111111
1
дададзена

Усталюйце некаторыя ўмовы і ўвесці простую зменную дапамогу.

L = 6, x = 3 , y = 2 introduce d = x - y = 1

Condition: if the list of the next number hypotetical value and the previous x - 1 elements values has a number of 0-digits > d next number concrete value must be 1, otherwise add two brances with both 1 and 0 as concrete value.

Start: check(Condition) => both 0,1 due to number of total zeros in the 0-count check.

Empty => add 0 and 1

Крок 1: Праверка (Condition)

0 (number of next value if 0 and previous x - 1 zeros > d(=1)) -> add 1 to sequence
1 -> add both 0,1 in two different branches

Крок 2: праверка (Стан)

01 -> add 1

10 -> add 1
11 -> add 0,1 in two different branches

Крок 3:

011 -> add 0,1 in two branches

101 -> add 1 (the next value if 0 and prev x-1 seq would be 010, so we prune and set only 1)

110 -> add 1
111 -> add 0,1

Крок 4:

0110 -> obviously 1
0111 -> both 0,1

1011 -> both 0,1

1101 -> 1
1110 -> 1
1111 -> 0,1

Крок 5:

01101 -> 1
01110 -> 1
01111 -> 0,1

10110 -> 1
10111 -> 0,1

11011 -> 0,1
11101 -> 1
11110 -> 1
11111 -> 0,1

Крок 6 (Гатова):

011011 
011101 
011110
011111

101101 
101110 
101111

110110
110111

111011 
111101 
111110
111111

Цяпер палічыце. Я тэставаў для L = 6, х = 4 і у = 2 таксама, але разгледзець, каб праверыць алгарытм для асаблівых выпадкаў і пашыраных выпадкаў.

Note: I'm pretty sure some algorithm with Disposition Theory bases should be a really massive improvement of my algorithm.

0
дададзена
@Arun розніца аб генерацыі паслядоўнасці. Тут мы тэстуем на першым, а затым генераваць. У Neal адказ ён генеруе затым праверыць то падрэзаць. Гэта падобна на погляд у будучыні, магчыма, мы зможам пабудаваць лепшае рашэнне з гэтай адпраўной кропкі.
дададзена аўтар Francesco De Lisi, крыніца
Гэта падобна на адказ размясціў Ніл, але менш эфектыўным, паколькі ён пачынаецца з 1 лічбай і пераходзіць адтуль у той час як там мы пачынаем з й лічбамі
дададзена аўтар Arun, крыніца
На самай справе я думаю, што як больш-менш будзе займаць той жа час для запуску ..
дададзена аўтар Arun, крыніца

Падобна на тое, укладзеная цыкл будзе рабіць трук. Псевдокод (не тэставалася).

value = '0101010111110101010111'  //change this line to format you would need
for (i = 0; i < (Len-x); i++) {   //loop over value from left to right
     kount = 0
     for (j = i; j < (i+x); j++) {//count '1' bits in the next 'x' bits
         kount += value[j]        //add 0 or 1
         if kount >= y then return success
     }
}
return fail
0
дададзена
Я няправільна вытлумачыў праблему, так што я змяніў маё псевдокод. Паколькі Len з'яўляецца знакавым цэлым, ёсць толькі каля 4 мільярдаў значэння, каб праверыць, калі лік складае 32 біт (я мяркую, што адмоўныя лікі справядлівыя і.) Для аптымізацыі, я б думаць аб праглядальнаму табліцах.
дададзена аўтар Marichyasana, крыніца
Гэты код правярае, што адзін асобнік двайковага ліку даўжыні Len задавальняе ўмова. Праблема заключаецца ў тым, каб знайсці, колькі такіх лікаў існуе. Вы сапраўды думаеце, што вы можаце паспрабаваць 2 ^ Len лічбы?
дададзена аўтар fjardon, крыніца

Наіўны падыход будзе дрэва-рэкурсіўны алгарытм.

Наш рэкурсіўны метад будзе паступова нарошчваць колькасць ўверх, напрыклад, было б пачаць у хххххх , вяртае суму выкліку з 1xxxxx і 0xXXXX , якія самі па сабе будзе вяртаць суму выкліку з <�код > 10 , 11 і 00 , 01 і г.д., за выключэннем, калі х/к ўмовы не выконваюцца для струны будзе будаваць па тэлефоне сам ён не ідзе па гэтым шляху, і калі вы знаходзіцеся ў тэрмінальным стане (пабудаваны шэраг патрэбнай даўжыні) вы вернецеся 1. (звярніце ўвагу, што, так як мы будуем радок уверх злева направа, вам не трэба правяраць х/у для ўсёй радкі, так і з улікам ізноў дадаванага лічбай!)

Вяртаючы суму па ўсіх выклікам, то ўсё вернутыя 1s аб'яднаюць разам і быць вернуты першапачатковы выклік, зраўнаваўся колькасць пабудаваных радкоў.

Паняцця не маю, што вялікая пазначэнне O для часовай складанасці для гэтага, яна не можа быць так дрэнна, як O (2 ^ п) * O (праверка X/Y ўмовы) , але гэта будзе падрэзаць шмат філіялаў ад дрэва ў большасці выпадкаў.

UPDATE: One insight I had is that all branches of the recursive tree can be 'merged' if they have identical last x digits so far, because then the same checks would be applied to all digits hereafter so you may as well double them up and save a lot of work. This now requires building the tree explicitly instead of implicitly via recursive calls, and maybe some kind of hashing scheme to detect when branches have identical x endings, but for large length it would provide a huge speedup.

0
дададзена
Я думаю, што выбар крыху ёсць нейкая прычына. Можа быць, лік уваходжанняў ў ў й старажытных біт паслядоўнасці L мае выгляд формулы (перастаноўка? Макс/мін адлегласць паміж элементамі?). Я буду абнаўляць, калі я знайсці рашэнне!
дададзена аўтар Francesco De Lisi, крыніца
Гэта доўгі час падыход. І пытанне «Колькі лік можа быць згенераваны, якія задавальняюць гэтай умове?». З вашага алгарытму Len = 200 ваш адказ будзе доўжыцца гадамі.
дададзена аўтар Francesco De Lisi, крыніца
@Francesco De Lisi Я думаў, аднаго з магчымага паскарэння, у вас ёсць якія-небудзь іншыя ідэі?
дададзена аўтар Patashu, крыніца
@Francesco De Lisi Так, гэта сапраўды адчувае сябе вельмі павольна, але пытанне не кажа: «Як бы я напісаць алгарытм, які вырашае яго з часовай складанасцю O (л) або лепш», так што я проста напісаў адно, што лёгка даказаць працы: )
дададзена аўтар Patashu, крыніца

Мой падыход заключаецца пачаць атрымліваць усе двайковыя лікі з мінімальным лікам 1, якая з'яўляецца досыць лёгка, вы проста атрымліваеце кожную унікальную перастаноўку двайковага ліку даўжынёй х с у 1-х, і цыкла кожнага унікальны перастановак «Len» раз. Гартаць 0 біт гэтага насення ў кожнай камбінацыі магчыма, мы гарантавана перабрацца ўсе двайковыя лікі, якія адпавядаюць крытэрам.

from itertools import permutations, cycle, combinations

def uniq(x):
    d = {}
    for i in x:
        d[i]=1
    return d.keys()


def findn( l, x, y ):
    window = []
    for i in xrange(y):
        window.append(1)
    for i in xrange(x-y):
        window.append(0)

    perms = uniq(permutations(window))
    seeds=[]
    for p in perms:
        pr = cycle(p)
        seeds.append([ pr.next() for i in xrange(l) ]) ###a seed is a binary number fitting the criteria with minimum 1 bits

    bin_numbers=[]
    for seed in seeds:
        if seed in bin_numbers: continue
        indexes = [ i for i, x in enumerate(seed) if x == 0] ### get indexes of 0 "bits"
        exit = False
        for i in xrange(len(indexes)+1):
            if( exit ): break
            for combo in combinations(indexes, i): ### combinatorically flipping the zero bits in the seed
                new_num = seed[:]
                for index in combo: new_num[index]+=1
                if new_num in bin_numbers:
                    ### if our new binary number has been seen before
                    ### we can break out since we are doing a depth first traversal
                    exit=True
                    break
                else:
                    bin_numbers.append(new_num)

    print len(bin_numbers)

findn(6,3,2)

Рост гэтага падыходу з'яўляецца тое, безумоўна, экспанентным, але я думаў, што я падзялю свой падыход у выпадку гэта дапамагае хто-то дабрацца да ніжняга рашэння складанасці ...

0
дададзена

Такім чынам, у серыі Len двайковых лічбаў, вы шукаеце й-доўгі сегмент, які змяшчае ў 1-х ..

See the execution: http://ideone.com/xuaWaK

Вось мой алгарытм ў Java:

import java.util.*;
import java.lang.*;

class Main
{
    public static ArrayList solve (String input, int x, int y)
    {
        int s = 0;
        ArrayList matches = new ArrayList();
        String segment = null;

        for (int i=0; i<(input.length()-x); i++)
        {
            s = 0;
            segment = input.substring(i,(i+x));

            System.out.print(" i: "+i+" ");

            for (char c : segment.toCharArray())
            {
                System.out.print("*");

                if (c == '1')
                {
                    s = s + 1;
                }
            }

            if (s == y)
            {
                matches.add(segment);
            }

            System.out.println();
        }

        return matches;
    }

    public static void main (String [] args)
    {
        String input = "011010101001101110110110101010111011010101000110010";

        int x = 6;

        int y = 4;

        ArrayList matches = null;

        matches = solve (input, x, y);

        for (String match : matches)
        {
            System.out.println(" > "+match);
        }

        System.out.println(" Number of matches is " + matches.size());
    }
}
0
дададзена
@KhaledAKhunaifer: Я праверыў спасылку, і толькі нешматлікія з паведамленых матчаў фактычна супадае.
дададзена аўтар Marichyasana, крыніца
@Arun выкарыстоўваць matches.size (), каб атрымаць колькасць
дададзена аўтар Khaled.K, крыніца
@Marichyasana праверыць гэта зараз, гэта працуе
дададзена аўтар Khaled.K, крыніца
@Arun праверыць спасылку я падаў, убачыць выкананне
дададзена аўтар Khaled.K, крыніца
Не, ён не шукае аднаго х даўжынёй сегмента, а <�я> кожны </я> х-доўгі адрэзак у Len даўжынёй двайковай лічбы павінны ўтрымліваць Y з іх.
дададзена аўтар John Willemse, крыніца
Я не кажу, што ваш код не так, Вы не зразумелі маё пытанне, я шукаю для падліку двайковых лікаў пэўнай даўжынёй, які задавальняе мае крытэры
дададзена аўтар Arun, крыніца
так, я шукаю для ліку такіх двайковых лікаў, якія могуць быць згенераваныя, якія задавальняюць крытэры, а не для праверкі, калі зададзены лік задавальняе ўмова
дададзена аўтар Arun, крыніца

Колькасць узораў даўжыні X, якія ўтрымліваюць, прынамсі, Y 1 біт лічыльна. Для выпадку х == ў мы ведаем, што менавіта адна карціна 2 ^ х магчымых мадэляў, якія задавальняе крытэрам. Пры меншым у мы павінны сумаваць колькасць мадэляў, якія маюць лішак 1 біт і колькасць мадэляў, якія маюць дакладна Y біт.

 choose(n, k) = n!/k! (n - k)!

 numPatterns(x, y) {
     total = 0
     for (int j  = x;  j >= y; j--)
        total += choose(x, j)
     return total
 }

Напрыклад :

X = 4, Y = 4 : 1 pattern
X = 4, Y = 3 : 1 + 4 = 5 patterns
X = 4, Y = 2 : 1 + 4 + 6 = 11 patterns
X = 4, Y = 1 : 1 + 4 + 6 + 4 = 15 patterns
X = 4, Y = 0 : 1 + 4 + 6 + 4 + 1 = 16 
  (all possible patterns have at least 0 1 bits)

Дык няхай M -число X патэрны даўжыні, якія задавальняюць Y крытэры. Цяпер, што X даўжыня кодавай камбінацыі з'яўляецца падмноствам N біт. Ёсць (N - х + 1) "акно" пазіцыі для шаблону на поўдзень, а 2 ^ N магчыма за ўсё мадэляў. Калі мы пачнем з любой з нашых M шаблоны, мы ведаем, што далучаючы 1 направа і пераход да наступнага акна прывядзе да аднаго з нашых вядомых M ўзоры. Пытанне ў тым, колькі з M мадэлі мы можам дадаць 0 на, зрух направа, і да гэтага часу дзейсны ўзор у M ?

Так як мы дадалі нуль, мы павінны быць альбо зрушэнне ад нуля, ці мы павінны быць ужо ў M , дзе мы маем лішак 1 біт. Каб перавярнуць, што вакол, мы можам спытаць, колькі з M ўзоры маюць дакладна Y біты і пачаць з 1 . Што ж, як «колькі мадэляў даўжыні X-1 Папрасіць Y-1 біты», пра якія мы ведаем, як адказаць:

shiftablePatternCount = M - choose(X-1, Y-1)

Так, пачынаючы з магчымасцямі M, мы маем намер павялічыць на shiftablePatternCount калі мы слізгаюць направа. Усе мадэлі ў новым акне ў наборы M , з некаторымі ўзорамі ў цяперашні час дублюецца. Мы збіраемся перакладаць некалькі разоў, каб запоўніць N па (N - X) , кожны раз павялічваючы колькасць на shiftablePatternCount , так поўны адказ павінен быць:

totalCountOfMatchingPatterns = M + (N - X)*shiftablePatternCount
  • змяніць - зразумеў памылку. Мне трэба, каб злічыць дублікаты ссоўвае шаблонаў, якія вы атрымалі. Я думаю, што гэта выканальна. (Праект яшчэ)
0
дададзена
  • Я не ўпэўнены, што мой адказ, але вось мой view.just зірнуць на яго,

  • <�Літый> <�р> Len = 4, </р> <�Літый> х = 3, <�Літый> <�р> у = 2. </Р>
  • <�р> я проста ўзяў дзве карціны, таму што шаблон павінен утрымліваць, па меншай меры, у 1. Да
  • <�Літый> <�р> Х 1 Х 1 </р> <�Літый> <�р> 1 X 1 X </р>
  • <�р> X - уяўляе не клапоціцца
  • <�Літый> <�р> Зараз разлічваць на 1-ым выразы 2 1 1 2 = 4 </р> <�Літый> <�р> і для 2-га выразы 1 2 1 2 = 4 </р> <�Літый> <�р> а 2 мадэль з'яўляецца агульным паміж абодвума так мінус 2..so будзе ўсяго 6 пар, якія задавальняюць умове. </Р>
0
дададзена
Такім чынам, ваша рашэнне патрабуе першых генерацыі шаблонаў? Гэта праблема, таму што гэта зойме занадта шмат часу, каб генераваць ўсе мадэлі. І тое, што логіка падставіўшы X для 2-х і -2 у канцы? Таксама 1 х 1 х ня задавальняе ўмове, так як прымаючы апошнія 3 лічбы, ёсць не 2 1-х
дададзена аўтар Arun, крыніца

Я, здараецца, выкарыстоўваючы algoritem падобную вашай праблемы, спрабуючы знайсці спосаб палепшыць яго, я знайшоў ваш пытанне. Так што я буду дзяліцца

static int GetCount(int length, int oneBits){
int result = 0;
double count = Math.Pow(2, length);
    for (int i = 1; i <= count - 1; i++)
    {
        string str = Convert.ToString(i, 2).PadLeft(length, '0');
        if (str.ToCharArray().Count(c => c == '1') == oneBits)
        {
            result++;
        }
    }
    return result;
}

не вельмі эфектыўныя я думаю, але Elegent рашэння.

0
дададзена