Форум программистов, компьютерный форум 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. Просмотров 2894. Ответов 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
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
10.04.2013, 20:30 #16
yutr777, понимаете, в таком случае задача действительно сложная и требует некоторое время для решения.
Но сложность её начинается вот откуда: После того, как мы заметим, что если у нас для каждого разряда X найдётся всего 2 варианта разряда в таких парах, то логично, что всего у нас таких чисел 2^(длина x в двоичной системе), но это без учёта следующих факторов: мы не отбросили числа с лидирующими нулями и не отбросили числа, которые кратны n и m и это и есть проблема.

Добавлено через 3 минуты
я там подправил
0
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 20:36  [ТС] #17
Цитата Сообщение от Ternsip Посмотреть сообщение
yutr777, понимаете, в таком случае задача действительно сложная и требует некоторое время для решения.
Но сложность её начинается вот откуда: После того, как мы заметим, что если у нас для каждого разряда X найдётся всего 2 варианта разряда в таких парах, то логично, что всего у нас таких чисел 2^n, но это без учёта следующих факторов: мы не отбросили числа с лидирующими нулями и не отбросили числа, которые больше n и m и это и есть проблема.
можно немного поточнее объяснить вот про пары чисел,т.е. я перевожу в двоичную систему дальше смотрю что стоит на i-ом месте(что такое i?), если 0,0 и там и там то Ок идем дальше....если 1,1 я не понял(((
вообщем чуть чуть больше объясните или примерчик киньте)

Добавлено через 4 минуты
просто я до конца не могу понять, что именно и как нужно считать
0
nonedark2008
914 / 653 / 137
Регистрация: 28.07.2012
Сообщений: 1,767
10.04.2013, 20:38 #18
Первое упрощение: Из сравнимости по модулю следует, что A = k1*N B=k2*M. Так что скакать можем с шагом N и M. Второе:
Цитата Сообщение от yutr777 Посмотреть сообщение
A⊕B=X
Точно не уверен, но мне почему-то кажется, что если нам известны A и X, то мы можем вычислить B. И наверно будет так: B = A⊕X, т.е. нам достаточно скакать тока по A, а B вычислять по формуле. А далее проверяем B % M == 0. Как-то так, больше не придумал >_>
1
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
10.04.2013, 20:40 #19
yutr777, Как видно на картинке, если нет ограничений (A mod N) == 0 и (B mod M) == 0 и A < 2^k и И B < 2^K что 2^(длина x в двоичной системе) и есть ответ
0
Миниатюры
Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000%  
nonedark2008
914 / 653 / 137
Регистрация: 28.07.2012
Сообщений: 1,767
10.04.2013, 20:48 #20
Будет вот так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main( void )
{
  UINT64 K = 3, N = 1, M = 2, X = 5;
  UINT64 A, B;
 
  for (A = 0; A < 1 << K; A += N)
  {
    B = A ^ X;
    if (B % M == 0)
      cout << '(' << A << ',' << B << ')' << endl;
  }
  system("pause");
  return 0;
}
2
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
10.04.2013, 20:50 #21
nonedark2008, Вы совершенно правы! Я согласен с вашим решением)
0
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 20:53  [ТС] #22
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Будет вот так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main( void )
{
  UINT64 K = 3, N = 1, M = 2, X = 5;
  UINT64 A, B;
 
  for (A = 0; A < 1 << K; A += N)
  {
    B = A ^ X;
    if (B % M == 0)
      cout << '(' << A << ',' << B << ')' << endl;
  }
  system("pause");
  return 0;
}

а на каком это языке???,,,, просто Dev C++ не хочет компилить(
0
nonedark2008
914 / 653 / 137
Регистрация: 28.07.2012
Сообщений: 1,767
10.04.2013, 20:56 #23
Цитата Сообщение от yutr777 Посмотреть сообщение
а на каком это языке???
Это C++ =) Попробуй заменить UINT64 на unsigned __int64, либо на unsigned long long, либо просто на unsigned если все остальное не фурычит
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
10.04.2013, 20:56 #24
yutr777,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
int main(){         
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    long long K = 3, N = 1, M = 2, X = 5;
    scanf("%I64d%I64d%I64d%I64d", &N, &M, &K, &X);
    long long ans = 0;
    for (long long A = 0; A < (1 << K); A += N){
      long long B = A ^ X;
      if (B % M == 0 && B < (1<<K)) //небольшой фикс
        ans++;
    }
    printf("%I64d", ans);
    system("pause");
    return 0;
}
Решение nonedark2008 верно. Но можно решить и комбинаторной формулой)
0
nonedark2008
914 / 653 / 137
Регистрация: 28.07.2012
Сообщений: 1,767
10.04.2013, 20:58 #25
Просто UINT64 - это мой темплейт для unsigned __int64.
0
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 21:06  [ТС] #26
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Просто UINT64 - это мой темплейт для unsigned __int64.
парни, что-то не фурычит....компиляцию проваливает О_о на компе все окау а тут....

Добавлено через 3 минуты
Парни,облом((((
свалил время на 37 тесте...((( пэчаль беда(
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
10.04.2013, 21:08 #27
yutr777, а сколько времени отводится ? Вы где решаете (любопытство)?
0
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 21:11  [ТС] #28
Цитата Сообщение от Ternsip Посмотреть сообщение
yutr777, а сколько времени отводится ? Вы где решаете (любопытство)?
чемпионат БГУИР по программированию)))


Добавлено через 15 секунд
только ТСССС!)))
молчим)
0
nonedark2008
914 / 653 / 137
Регистрация: 28.07.2012
Сообщений: 1,767
10.04.2013, 22:01 #29
Хмм. А вообще какие ограничения?
Наверняка фейлится при больших N. Можно ли например вообще взять и цикл распаралелить?

Добавлено через 9 минут
Скорее всего тест фейлится когда N и M малы, а K - большое. Тогда происходит слишком много итераций.
0
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 22:10  [ТС] #30
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Хмм. А вообще какие ограничения?
Наверняка фейлится при больших N. Можно ли например вообще взять и цикл распаралелить?

Добавлено через 9 минут
Скорее всего тест фейлится когда N и M малы, а K - большое. Тогда происходит слишком много итераций.
да, скорее всего именно так и есть(
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.04.2013, 22:10
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
30
Yandex
Объявления
10.04.2013, 22:10
Ответ Создать тему
Опции темы

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