Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.82
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
#1

Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% - C++

10.04.2013, 19:16. Просмотров 2913. Ответов 59
Метки нет (Все метки)

≡ вот эта закарюка меня пугает,подскажите, что это?
и решите пожалуйста задачку
Требуется для заданных K N M и X найти количество пар чисел A и B таких, что A≡0 (mod N), B≡0 (mod M), 0≤A,B<2 K , A⊕B=X.

Формат входных данных

Первая строка содержит целые числа K N M и X (1≤K≤30, 1≤N,M,X≤2×10(в девятой)9 ).

Формат результата

Выведите искомое количество пар чисел.

Примеры

Входные данные Результат работы
3 1 2 5
4
Примечания

Искомые пары (1;4), (3;6), (5;0) и (7;2).
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.04.2013, 19:16
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% (C++):

Булева Алгебра) - Логика и множества
Помогите пожалуйста)Ни как не могу понять,как минимизировать то,что стоит в скобках Пускай НЕ-это ! х4*х5*(!х1*х2*х3+х1*!х2*!х3) или...

Булева Алгебра - Логика и множества
Ребят, помогите пожалуйста с работой, 1,2,7 сделал, с остальными не могу переварить.

Булева алгебра - Дискретная математика
Помогите пожалуйста решить задания. Просто завтра контрольная, а в ДМ не очень шарю Правила, 5.16, 5.18. Задания набирать ручками....

Булева Алгебра - Логика и множества
Проверти пожалуйста правильно ли выполнил минимизацию ? Меня сильно смущает (Х1Х2Х3) что не сокращается.

Булева алгебра - Математика
при умножении x на y по and(&amp;), получаем некое с, как потом зная с и x найти y ?

Булева алгебра - Алгебра
Приветствую. Прошу помочь с решением данного вида задания. Заранее благодарен. Для заданных функций f1 и f2 построить таблицу истинности....

59
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
10.04.2013, 19:25 #2
Цитата Сообщение от yutr777 Посмотреть сообщение
≡ вот эта закарюка меня пугает,подскажите, что это?
читается как "тождественно равно"
0
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 19:36  [ТС] #3
Цитата Сообщение от ya_noob Посмотреть сообщение
читается как "тождественно равно"
а что оно обозначает?
0
abit
271 / 270 / 34
Регистрация: 03.02.2013
Сообщений: 754
10.04.2013, 19:45 #4
эта запись A≡0 (mod N) означает, что A делится на N без остатка (т.е. A должно быть кратно N)

собстна как найти количество пар мне в голову приходит только решение в лоб - сделать вложенный цикл по A и B в котором написать
C++
1
 if((A^B)==X) ++paircounter;
но может есть и более оптимальное решение, надо полистать комбинаторику и теорию чисел

собстна я бы написал вам решение в лоб, но что-то у вас в условии не сходится

тут
0≤A,B<2 K
сказано чётко, что A и B должны быть строго меньше 2K насолько я вижу
а ваши две пары из примера противоречат условию
(3;6) и (7;2)
в первом случае B=6=2*K (не меньше)
во втором случае A=7>2*K (больше)

проверьте условие
1
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 19:52  [ТС] #5
Цитата Сообщение от abit Посмотреть сообщение
эта запись A≡0 (mod N) означает, что A делится на N без остатка (т.е. A должно быть кратно N)

собстна как найти количество пар мне в голову приходит только решение в лоб - сделать вложенный цикл по A и B в котором написать
C++
1
 if((A^B)==X) ++paircounter;
но может есть и более оптимальное решение, надо полистать комбинаторику и теорию чисел

собстна я бы написал вам решение в лоб, но что-то у вас в условии не сходится

тут


сказано чётко, что A и B должны быть строго меньше 2K насолько я вижу
а ваши две пары из примера противоречат условию
(3;6) и (7;2)
в первом случае B=6=2*K (не меньше)
во втором случае A=7>2*K (больше)

проверьте условие
условие верное...некоторые команды сдали эту задачу...я никак не могу(
0
abit
271 / 270 / 34
Регистрация: 03.02.2013
Сообщений: 754
10.04.2013, 20:00 #6
а, дошло)

вот в общем решение в лоб

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# include <iostream>
 
int main()
{
    unsigned int paircounter=0;
    unsigned int K,N,M,X;
    
    std::cin >> K >> N >> M >> X;
    
    for(unsigned int A = 0; A!=2*K; ++A)
     for (unsigned int B = 0; B!=2*K; ++B)
     if(((A^B)==X)&&(A%N==0)&&(B%N==0)) ++paircounter;          
    std::cout <<paircounter<<std::endl;;
    return 0;
 
}
Добавлено через 5 минут
все же искомые пары не те, что вы указали а
(0;5),(1;4),(4;1) и (5;0)

так и передайте составителям задач
0
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 20:01  [ТС] #7
Цитата Сообщение от abit Посмотреть сообщение
эта запись A≡0 (mod N) означает, что A делится на N без остатка (т.е. A должно быть кратно N)

собстна как найти количество пар мне в голову приходит только решение в лоб - сделать вложенный цикл по A и B в котором написать
C++
1
 if((A^B)==X) ++paircounter;
но может есть и более оптимальное решение, надо полистать комбинаторику и теорию чисел

собстна я бы написал вам решение в лоб, но что-то у вас в условии не сходится

тут


сказано чётко, что A и B должны быть строго меньше 2K насолько я вижу
а ваши две пары из примера противоречат условию
(3;6) и (7;2)
в первом случае B=6=2*K (не меньше)
во втором случае A=7>2*K (больше)

проверьте условие
я задал вопрос...это два в К-ой степени
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
10.04.2013, 20:03 #8
yutr777, задача чрезвычайно простая, особенно, учитывая что k <= 30. Вот, если n,m,K < 10^18 уже другое дело
0
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 20:04  [ТС] #9
Цитата Сообщение от Ternsip Посмотреть сообщение
yutr777, задача чрезвычайно простая, особенно, учитывая что k <= 30. Вот, если n,m,K < 10^18 уже другое дело
решите пожалуйста, умоляю вас....я бы даже на колени стал...очень важно, чтобы вы помогли...Спасибо!
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
10.04.2013, 20:07 #10
yutr777, для вашей задачи abit уже написал решение
0
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 20:08  [ТС] #11
Цитата Сообщение от Ternsip Посмотреть сообщение
yutr777, для вашей задачи abit уже написал решение
но там не 2*k а 2^k
0
abit
271 / 270 / 34
Регистрация: 03.02.2013
Сообщений: 754
10.04.2013, 20:15 #12
Цитата Сообщение от yutr777 Посмотреть сообщение
но там не 2*k а 2^k
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# include <iostream>
 
int main()
{
    unsigned int paircounter=0;
    unsigned int K,N,M,X;
    
    std::cin >> K >> N >> M >> X;
    
    for(unsigned int A = 0; A!=2<<(K-1); ++A)
     for (unsigned int B = 0; B!=2<<(K-1); ++B)
     if(((A^B)==X)&&(A%N==0)&&(B%M==0)) 
        ++paircounter; 
 
    std::cout <<paircounter<<std::endl;;
    return 0;
 
}
Добавлено через 1 минуту
всё, верно... с парами тоже
так можно поглядеть на эти пары:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# include <iostream>
 
int main()
{
    unsigned int paircounter=0;
    unsigned int K,N,M,X;
    
    std::cin >> K >> N >> M >> X;
    
    for(unsigned int A = 0; A!=2<<(K-1); ++A)
     for (unsigned int B = 0; B!=2<<(K-1); ++B)
     if(((A^B)==X)&&(A%N==0)&&(B%M==0)) 
      {
        std::cout <<"("<<A<< ","<<B<<")"<<std::endl;;
        ++paircounter; 
      }
    std::cout <<paircounter<<std::endl;;
    return 0;
 
}
старый мой бред не читайте) там ошибка была... не углядел, а здесь уже для 2^K
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
10.04.2013, 20:18 #13
yutr777, решается она так: Заметим, что в двоичной записи числа X: в i-м разряде если стоит 0, то в числах a,b из всех пар, на данной позиции должны стоять либо 0,0 либо 1,1, если там 1 то должны стоять 1,0 либо 0,1 таким образом можно комбинаторно определить сколько всего же таких чисел. Ну раз вам это так нужно я попробую))

Добавлено через 37 секунд
abit, введите у себя k = 30
1
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 20:20  [ТС] #14
Цитата Сообщение от Ternsip Посмотреть сообщение
yutr777, решается она так: Заметим, что в двоичной записи числа X: в i-м разряде если стоит 0, то в числах a,b из всех пар, на данной позиции должны стоять либо 0,0 либо 1,1, если там 1 то должны стоять 1,0 либо 0,1 таким образом можно комбинаторно определить сколько всего же таких чисел. Ну раз вам это так нужно я попробую))

Добавлено через 37 секунд
abit, введите у себя k = 30
спасибо)
просто это действительно вопрос жизни и смерти
0
abit
271 / 270 / 34
Регистрация: 03.02.2013
Сообщений: 754
10.04.2013, 20:25 #15
Цитата Сообщение от Ternsip Посмотреть сообщение
Добавлено через 37 секунд
abit, введите у себя k = 30
ну я предупреждал, что это влоб... работать будет, но медленно
если это олимпиадная задача - то там есть ограничения на время и так делать не стоит
конечно предпочтительнее комбинаторику влепить, но тогда мне не совсем понятно как получить сами пары чисел, ну в общем как сделаете, погляжу )
0
10.04.2013, 20:25
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.04.2013, 20:25
Привет! Вот еще темы с ответами:

Булева алгебра - Логика и множества
Проверить эквивалентность формул А и В, используя основные аксиомы и теоремы булевой алгебры. помогите пожалуйста я вообще не понимаю че...

Булева алгебра - Логика и множества
Помогите, пожалуйста, доказать аналитическим путём. заранее спасибо. \left(\bar{A} \bigcup B\right)+\left(\bar{B}\bigcup A...

Булева алгебра - Логика и множества
Всем привет Ребята, никто не сталкивался с доказательством свойств булевой алгебры, очень много литературы перерыл, но не нашёл ничего...

Булева Алгебра - Алгебра
Упростите логические функции, используя аксиомы, тождества и законы алгебры логики. а) F=(НЕ X1)*X2 + X1*X2 б) F=X1+X1*X2+X3 в) F=(НЕ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru