|
umka
|
|
polar bear
|
|
|
|
|
|
|
Рег.: 17.09.2003
|
|
Сообщений: 24023
|
|
Из: Москва
|
|
Рейтинг: -11
|
|
задачка
19.02.2005 11:51
|
|
|
во задачку вспомнил на зачете по философии прочитал на доске
f(x_1,...,x_n)=x_1x_2+...+x_(n-1)x_n
сложение по модулю 2
найти число наборов на которых функция =1
|
Don't get attached to anything you can't walk out on 30 seconds... |
|
|
PEHAT
|
|
|
|
|
|
|
|
|
Рег.: 13.05.2004
|
|
Сообщений: 130
|
|
Из: г.Астрахань
|
|
Рейтинг: 0
|
|
|
#реш_n=2^{n-1}
Доказывается по индукции. Для n=1 верно.
Добавляем новую переменную x_{n+1} и рассматриваем два случая x_{n+1}=0,1.
В каждом случае решений #реш_n
#реш_{n+1}=2*#реш_n=2^n
|
|
|
umka
|
|
polar bear
|
|
|
|
|
|
|
Рег.: 17.09.2003
|
|
Сообщений: 24023
|
|
Из: Москва
|
|
Рейтинг: -11
|
|
|
для n=3
получается 3 решения, и вообще я мягко говоря не понял почему там в каждом случае для 0 и 1 одно и тоже число решений
|
Don't get attached to anything you can't walk out on 30 seconds... |
|
|
bubble
|
|
TeddyBear
|
|
|
|
|
|
|
Рег.: 17.11.2004
|
|
Сообщений: 945
|
|
|
|
Рейтинг: 215
|
|
|
|
|
|
PEHAT
|
|
|
|
|
|
|
|
|
Рег.: 13.05.2004
|
|
Сообщений: 130
|
|
Из: г.Астрахань
|
|
Рейтинг: 0
|
|
|
В ответ на:
для n=3 получается 3 решения
Да ну!
x_1x_2x_3 = 011 или 110
А ты про какую функцию спрашиваешь, при n=3 я имею ввиду
x_1x_2+x_2x_3
|
|
|
umka
|
|
polar bear
|
|
|
|
|
|
|
Рег.: 17.09.2003
|
|
Сообщений: 24023
|
|
Из: Москва
|
|
Рейтинг: -11
|
|
|
ну это 2
|
Don't get attached to anything you can't walk out on 30 seconds... |
|
|
Pooh
|
|
|
|
|
|
|
|
|
Рег.: 23.10.2003
|
|
Сообщений: 5399
|
|
|
|
Рейтинг: 3869
|
|
|
Для n = 4:
f = x_1*x_2 + x_2*x_3 + x_3*x_4
0000 0
0001 0
0010 0
0100 0
0101 0
0110 1
0111 0
1000 0
1001 0
1010 0
1011 1
1100 1
1101 1
1110 0
1111 1
Получилось 5 решений
ЗЫ Надо ввести две последовательсности - кол-во решений с 0 на конце, кол-во решений с 1 на конце и составить на них реккурентности и решить их.
Редактировал Pooh (19.02.2005 12:49)
|
|
|
PEHAT
|
|
|
|
|
|
|
|
|
Рег.: 13.05.2004
|
|
Сообщений: 130
|
|
Из: г.Астрахань
|
|
Рейтинг: 0
|
|
|
Да это глюк был, я почему-то считал, что x_1x_2+x_2x_3+x_3 = x_1x_2+x_2(x_3+1)
|
|
|
umka
|
|
polar bear
|
|
|
|
|
|
|
Рег.: 17.09.2003
|
|
Сообщений: 24023
|
|
Из: Москва
|
|
Рейтинг: -11
|
|
|
короче у меня получается послед.фиб
|
Don't get attached to anything you can't walk out on 30 seconds... |
|
|
Pooh
|
|
|
|
|
|
|
|
|
Рег.: 23.10.2003
|
|
Сообщений: 5399
|
|
|
|
Рейтинг: 3869
|
|
|
Пости ответ на n = 6 
|
|
|
umka
|
|
polar bear
|
|
|
|
|
|
|
Рег.: 17.09.2003
|
|
Сообщений: 24023
|
|
Из: Москва
|
|
Рейтинг: -11
|
|
|
8
|
Don't get attached to anything you can't walk out on 30 seconds... |
|
|
Pooh
|
|
|
|
|
|
|
|
|
Рег.: 23.10.2003
|
|
Сообщений: 5399
|
|
|
|
Рейтинг: 3869
|
|
|
Вот ведь пропустил последовательность 0011. Так решений для n = 4 получается 6.
00000 0 10000 0
00001 0 10001 0
00010 0 10010 0
00011 1 10011 1
00100 0 10100 0
00101 0 10101 0
00110 1 10110 1
00111 0 10111 0
01000 0 11000 1
01001 0 11001 1
01010 0 11010 1
01011 1 11011 0
01100 1 11100 0
01101 1 11101 0
01110 0 11110 1
01111 1 11111 0
12 решений для n = 5
|
|
|
Pooh
|
|
|
|
|
|
|
|
|
Рег.: 23.10.2003
|
|
Сообщений: 5399
|
|
|
|
Рейтинг: 3869
|
|
|
|
|
|
umka
|
|
polar bear
|
|
|
|
|
|
|
Рег.: 17.09.2003
|
|
Сообщений: 24023
|
|
Из: Москва
|
|
Рейтинг: -11
|
|
|
короче рек.формула такая S_n=2^(n-2)+2S_(n-2)
s_1=0 (так надо)
s_2=1
s_3=2
s_4=6
s_5=12
s_6=28
s_7=32+24=56
s_8=64+56=120
s_9=128+112=240
|
Don't get attached to anything you can't walk out on 30 seconds... |
|
|
RSA
|
|
|
|
|
|
|
|
|
Рег.: 09.09.2003
|
|
Сообщений: 1091
|
|
Из: Б-1149л
|
|
Рейтинг: -319
|
|
|
n = 3
011
110
Итого решений: 2
n = 4
0011
0110
1011
1100
1101
1111
Итого решений: 6
n = 5
00011
00110
01011
01100
01101
01111
10011
10110
11000
11001
11010
11110
Итого решений: 12
n = 6
000011
000110
001011
001100
001101
001111
010011
010110
011000
011001
011010
011110
100011
100110
101011
101100
101101
101111
110000
110001
110010
110100
110101
110111
111011
111100
111101
111111
Итого решений: 28
Редактировал RSA (19.02.2005 13:24)
|
|
|
Pooh
|
|
|
|
|
|
|
|
|
Рег.: 23.10.2003
|
|
Сообщений: 5399
|
|
|
|
Рейтинг: 3869
|
|
|
S_4 = 2^(4-2) + 2S_(4-2) = 4 + 2*S_2 = 4 + 2*1 = 6. Верно
S_5 = 2^(5-2) + 2*S_(5-2) = 8 + 2*S_3 = 8 + 2*2 = 12. Верно
Похоже на правду. Если оканчивается на 01 или 00, то в сумме 2*S_(n-2). Если на 10 или на 11, то в сумме 2^(n-2).
Правильная формула.
|
|
|
umka
|
|
polar bear
|
|
|
|
|
|
|
Рег.: 17.09.2003
|
|
Сообщений: 24023
|
|
Из: Москва
|
|
Рейтинг: -11
|
|
Re: задачка
[re: RSA]
19.02.2005 13:23
|
|
|
01110
00111 - откуда?
|
Don't get attached to anything you can't walk out on 30 seconds... |
|
|
Pooh
|
|
|
|
|
|
|
|
|
Рег.: 23.10.2003
|
|
Сообщений: 5399
|
|
|
|
Рейтинг: 3869
|
|
Re: задачка
[re: RSA]
19.02.2005 13:24
|
|
|
Редактировал Pooh (19.02.2005 13:26)
|
|
|
umka
|
|
polar bear
|
|
|
|
|
|
|
Рег.: 17.09.2003
|
|
Сообщений: 24023
|
|
Из: Москва
|
|
Рейтинг: -11
|
|
Re: задачка
[re: RSA]
19.02.2005 13:24
|
|
|
считай заново короче n=3 неправильно
|
Don't get attached to anything you can't walk out on 30 seconds... |
|
|
RSA
|
|
|
|
|
|
|
|
|
Рег.: 09.09.2003
|
|
Сообщений: 1091
|
|
Из: Б-1149л
|
|
Рейтинг: -319
|
|
|
Я писал раньше, чтобы сумма была 0 . Сейчас исправил на 1.
|
|
Список
Плоский
Дерево
