Последовательности

Discussion in 'С/С++, C#, Rust, Swift, Go, Java, Perl, Ruby' started by marcos, 11 Jan 2010.

  1. marcos

    marcos New Member

    Joined:
    8 Nov 2009
    Messages:
    111
    Likes Received:
    1
    Reputations:
    -5
    Всем привет!
    Подскажите как вывести количество последовательностей длины N из нулей и единиц, не содержащих двух единиц подряд?
     
  2. drim

    drim Member

    Joined:
    27 Aug 2009
    Messages:
    347
    Likes Received:
    33
    Reputations:
    4
    откуда и куда вывести? если из программы на STDOUT, то, обычно, оператор print помогает
     
  3. Algol

    Algol New Member

    Joined:
    29 May 2002
    Messages:
    1,759
    Likes Received:
    4
    Reputations:
    0
    Ну если в лоб решать - то просто перебирай всевозможные комбинации нулей и единиц, и считай тольке те, у которых нет двух единиц подряд...
     
  4. ][yZ

    ][yZ Member

    Joined:
    3 Mar 2009
    Messages:
    66
    Likes Received:
    46
    Reputations:
    10
    млин, это же легко...
    короче, заведем двухмерный массив a[i, j], где i - длина последовательности, j - на что оканчивается (0 или 1)

    a[1, 1] = 1
    a[1, 0] = 1

    потом, к нолику мы можем дописать или 0 или 1, т. е. a[i, 0] = a[i - 1, 0] + a[i - 1, 1]
    к единице только нолик, т.е. a[i, 1] = a[i - 1, 0]
    результат в a[n, 0] + a[n, 1]

    как-то так
     
    1 person likes this.
  5. desTiny

    desTiny Elder - Старейшина

    Joined:
    4 Feb 2007
    Messages:
    1,005
    Likes Received:
    444
    Reputations:
    94
    ][yZ, если ещё соптимайзить, то можно заметить, что две твои последовательности имеют вид:
    a_n = a_n-1 + b_n-1=a_n-1 + a_n-2
    b_n = a_n-1

    a_0=1; a_1=1 => a_n = n-1-ое число Фибоначчи F_n-1,
    ответ: a_n-1+F_n-1 = F_n-1 + F_n-2 = F_n.
    /*с индексами мог напутать, но вроде правда*/
     
    2 people like this.
  6. slesh

    slesh Elder - Старейшина

    Joined:
    5 Mar 2007
    Messages:
    2,704
    Likes Received:
    1,224
    Reputations:
    455
    НУ я хз число фибоначи или когонить другова, чисто эксперементально рашил провести собственный опыт.

    Искать через перебор в данном случае очень не рационально.
    В большинстве случаев, там где есть перебор всех возможных комбинаций
    На конечном множестве, то такие вещи почти всегда имеют формулы.
    Или их можно вывести опытным путем.

    Вот небольшие рассуждения:

    Формула для полного числа комбинаций:
    K= 2 ^ N.
    И так.
    если N = 1 то K = 2 ^ 1 = 2
    0
    1
    Непоходят 0


    если N = 2 то K = 2 ^ 2 = 4

    00
    01
    10
    11
    Из низ видно что тока 1 неподходит.

    Если N = 3 то K = 2 ^ 3 = 8
    000
    001
    010
    011
    100
    101
    110
    111
    Из них 3 неподходит


    Если N = 4 то K = 2 ^ 4 = 16
    0000
    0001
    0010
    0011
    0100
    0101
    0110
    0111

    1000
    1001
    1010
    1011
    1100
    1101
    1110
    1111
    Из них 8 неподходит.

    Если N = 5 то K = 2 ^ 5 = 32

    00000
    00001
    00010
    00011
    00100
    00101
    00110
    00111

    01000
    01001
    01010
    01011
    01100
    01101
    01110
    01111

    10000
    10001
    10010
    10011
    10100
    10101
    10110
    10111

    11000
    11001
    11010
    11011
    11100
    11101
    11110
    11111

    Из них 19 не неподходит

    ВОт простые вычисления. далее Строим таблицу.
    N = длинна ряда
    K = число комбинаций
    G = Число подходящих вариант
    B = Число не подходящих вариантов


    0) N0 = 1 K0 = 2 G0 = 2 B0 = 0
    1) N1 = 2 K1 = 4 G1 = 3 B1 = 1
    2) N2 = 3 K2 = 8 G2 = 5 B2 = 3
    3) N3 = 4 K3 = 16 G3 = 8 B3 = 8
    4) N4 = 5 K4 = 32 G4 = 13 B4 = 19

    Теперь простейшим поиском закономерности можно найти вот что:

    G0 = 2
    G1 = G0 + 1
    G2 = G1 + G0
    G3 = G2 + G1
    G4 = G3 + G2

    теперь видна сразу закономерность распределения подходящих чисел
    и считатсья будет примерно так

    Code:
    const N = 5 ;
    var
      x : integer;
      G : integer;
      LastG : integer;
      Tmp : integer;
    begin
      LastG := 1;
      G := 2;
      for x := 1 to N do
      begin
        Tmp := G;
        G := G + LastG;
        LastG := Tmp;
      end;
      ShowMessage(inttostr(G));
    end;
    
     
    1 person likes this.
  7. desTiny

    desTiny Elder - Старейшина

    Joined:
    4 Feb 2007
    Messages:
    1,005
    Likes Received:
    444
    Reputations:
    94
    ][yZ предложил естественное динамическое решение
    я сказал общую формулу на его основании (хотя вообще это очевидно по другой причине: r_n = r_n-1 + r_n-2, так как мы могли взять любую последовательность длины n-1 и дописать "0" и любую длины n-2 и дописать "01")
    slesh - а ты изварщенец, батенька :))))
     
  8. Algol

    Algol New Member

    Joined:
    29 May 2002
    Messages:
    1,759
    Likes Received:
    4
    Reputations:
    0
    Почему извращенец ?
    Если есть аналитическое решение - то конечно его нужно использовать :)
     
  9. lukmus

    lukmus Elder - Старейшина

    Joined:
    18 Nov 2009
    Messages:
    384
    Likes Received:
    115
    Reputations:
    23
    А теперь будем рассуждать логически-математически:
    k(x) - функция количества чисел содержащих '11'
    k(0)=0
    k(1)=0
    k(2)=1

    11
    k(3)=3
    11 - число пришедшее от предыдущей разрядности
    110 - числа полученный добавлением в начало '11' и перебором
    111 - остальных свободных бит т.е. вида 11x

    k(4)= 8
    11
    110
    111
    1011
    1100
    1101
    1110
    1111

    С первыми 3-мя числами все ясно, они пришли от предыдущей разрядности. Последние четыре, то же ясны, они вида 11xx.
    И остаеться одно интересное число - 1011, будем условно называть такие числа - числа Лакмусачи (Lukmusacci) ))).

    k(5)=19
    Количество складываеться из:
    -8 чисел от предыдущей разрядности
    -8 чисел вида 11xxx
    -3 числа Лакмусачи

    k(6)=43
    Количество складываеться из:
    -19 чисел от предыдущей разрядности
    -16 чисел вида 11xxxx
    -8 чисел Лакмусачи

    Пронзительный читатель уже догадался к чему я виду:
    количество чисел Лакмусачи для разрядности n равно k(n-2) , посмотрите внимательно Лакмусачи для 6 равно количеству чисел содержащих '11' для 4.

    В итоге мы можем вывести эмпирическую функцию k(n):
    k(n)=k(n-2)+k(n-1)+2^(n-2), где k(n-2) - числа Лакмусачи,
    k(n-1) - числа пришедшие от прошлой разрядности, 2^(n-2) - числа вида 11x
    .
    Тем самым количество чисел не содержащих '11' для разрядности n равно: 2^(n) - k(n)=2^(n)-k(n-2)-k(n-1)-2^(n-2)
     
    1 person likes this.
  10. lukmus

    lukmus Elder - Старейшина

    Joined:
    18 Nov 2009
    Messages:
    384
    Likes Received:
    115
    Reputations:
    23
    Спомощью не сложных математических операций, можно апроксимировать эту функцию, не смотря на то что она дискретная.
    Моего компьютера хватила только на апроксимацию многочленом 13-ой степени.
    Тем самым получим не рекурсивную функцию вида y(x)=F(y(x-a1),y(x-a2),...,y(x-an)), полноценную функцию y=f(x)

    [​IMG]

    маткадовский файл
     
    #10 lukmus, 12 Jan 2010
    Last edited: 12 Jan 2010
  11. desTiny

    desTiny Elder - Старейшина

    Joined:
    4 Feb 2007
    Messages:
    1,005
    Likes Received:
    444
    Reputations:
    94
    k(n)=k(n-2)+k(n-1)+2^(n-2) - это неверный ответ, прости :)
     
  12. lukmus

    lukmus Elder - Старейшина

    Joined:
    18 Nov 2009
    Messages:
    384
    Likes Received:
    115
    Reputations:
    23
    перечитай, у меня все верно, там не учитываеться 0 т.е. начинается с 1 если что.
     
  13. slesh

    slesh Elder - Старейшина

    Joined:
    5 Mar 2007
    Messages:
    2,704
    Likes Received:
    1,224
    Reputations:
    455
    Млять, lukmus нахуя ты залил картинку на этот ёбаный обменник. // сори за мат.

    Зайдя туда появилась парочка назойливых банеров.
    А после comodo порадывал меня тем что опера запустила программу, а программка запустила другую программку и так далее.
    И как назло комод стол в режиме обучения по этому с радость пропустил всё.
    ------------
    Врубил комод на полную. Сделал ребут. И он заорал на прогу, которая по виду блокала экран )
    -----------
    Зато слил часть связки, и все exe. А там их 4 штуки )
     
    #13 slesh, 12 Jan 2010
    Last edited: 12 Jan 2010
  14. Fata1ex

    Fata1ex Elder - Старейшина

    Joined:
    12 Dec 2006
    Messages:
    703
    Likes Received:
    300
    Reputations:
    38
    Античат решает задачку оО
    я в шоке :D
     
  15. sn0w

    sn0w Статус пользователя:

    Joined:
    26 Jul 2005
    Messages:
    1,009
    Likes Received:
    1,115
    Reputations:
    327
    Code:
    //  s - pointer to block
    //	l - length of block
    //
    //  ret: 0 - no serial '1' detected
    //		 x - idx of first '1' (1-base)
    int check_fragment(char *s, int l)
    {
    	for(int i=0; i< l-1; i++)
    		if(s[i]=='1' && s[i+1]=='1')
    			return i+1; // avoid zerobase offset
    	return 0;	
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    
    	char *s01 = "1110101010";	// source 0/1
    	const int block_len = 5;	// N
    
    	int slen = strlen(s01);
    	int num_frags = 0, temp;
    
    	for(int i=0; i< slen; ){
    
    		if(strlen(&s01[i])<block_len)break;
    		temp = check_fragment(&s01[i], block_len);
    
    		if(temp==0){
    			i+= block_len;
    			num_frags++;
    			continue;
    		}
    		i+=temp;
    	}
    
    	printf("%d", num_frags);
    
    	return _getch();
    }
    
    
    те ес я правильно понял то в данном варианте

    char *s01 = "1110101010"; // source 0/1
    const int block_len = 5; // N

    вывод должен быть равен 1, как он и есть собсна.

    ...ес прально понял =)


    примерной такой вывод (N=5):

    0000000000 - 2
    1111111111 - 0
    0000110000 - 2
    1100000000 - 1
    0000000011 - 1
    1111110000 - 1
    1101010110 - 1
     
    #15 sn0w, 12 Jan 2010
    Last edited: 12 Jan 2010
  16. lukmus

    lukmus Elder - Старейшина

    Joined:
    18 Nov 2009
    Messages:
    384
    Likes Received:
    115
    Reputations:
    23
    извини, перезалил, просто вчера какой-то гал был и картинка покрайней мере у меня не отображалась с другого хостинга
     
  17. desTiny

    desTiny Elder - Старейшина

    Joined:
    4 Feb 2007
    Messages:
    1,005
    Likes Received:
    444
    Reputations:
    94
    Я прочитал вот это:
    >>k(x) - функция количества чисел содержащих '11'
    >>k(n)=k(n-2)+k(n-1)+2^(n-2)

    это (edit: оказывается)верно.
    Обозначим s(n) количество чисел разрядности ровно n, содержащих 11.
    Такие числа можно получить двумя способами:
    '10' . число, содержащее '11' длины (n-2) (получили k(n-2) чисел)
    '11' . любое число длины (n-2) (и ещё 2^(n-2))
    ( . - конкатенация строк)

    Значит, s(n) = k(n-2)+2^(n-2).

    Твоё k(n) = сумма по i=1..n s(i) = сумма по i=1..(n-1) s(i) + s(n)= k(n-1) + k(n-2) + 2^(n-2)

    твой ответ = этот
    хорошо :) У меня был баг :)
     
    #17 desTiny, 12 Jan 2010
    Last edited: 13 Jan 2010
  18. lukmus

    lukmus Elder - Старейшина

    Joined:
    18 Nov 2009
    Messages:
    384
    Likes Received:
    115
    Reputations:
    23
    а с чего ты взял что твоя формула и выводы верны, что составляешь тождество с моей функцией. По твоей формуле:
    n=4 => s(4)=s(2)+2^2=1+4=5, хотя для разрядности 4 существуют следующие числа с '11':
    11
    110
    111
    1011
    1100
    1101
    1110
    1111

    т.е. их 8
    s(5)=s(3)+2^3=3+8=11. хотя их 19:
    11
    110
    111
    1011
    1100
    1101
    1110
    1111
    10011
    10110
    10111
    11000
    11001
    11010
    11011
    11100
    11101
    11110
    11111


    а по крайней мере одна из ошибок твоей формулы, такая что в варианте:
    например для разрядности 3 никогда не получиться числа 112=310, минимальное будет число 110 т.к все числа разрядности n-2=3-1=1 это: 1 и 0, но там нет пустого множества.
     
  19. desTiny

    desTiny Elder - Старейшина

    Joined:
    4 Feb 2007
    Messages:
    1,005
    Likes Received:
    444
    Reputations:
    94
    ты меня не понял - я считаю функцию s(n) как ровно n-разрядное число.
    Но да, согласен, у меня там бага в строчке
    >>'10' . число, содержащее '11' длины (n-2) (получили s(n-2) чисел)
    правильно, конечно же,
    >>'10' . число, содержащее '11' длины (n-2) (получили k(n-2) чисел)
    так как я забыл, что мы не считаем числа, начинающиеся с 1.
    Так что правильный походу у тебя ответ, хоть ты его и не аргументировал :)

    тут нет ошибки
     
Loading...