Форум программистов, компьютерный форум 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. Просмотров 2860. Ответов 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).
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 построить таблицу истинности....

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
nonedark2008
903 / 642 / 131
Регистрация: 28.07.2012
Сообщений: 1,733
10.04.2013, 22:12 #31
Еще ко-че можно выжать из условия A,B <2^k. Т.е. выбирать только подходящие промежутки.
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 22:19  [ТС] #32
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Еще ко-че можно выжать из условия A,B <2^k. Т.е. выбирать только подходящие промежутки.
всмысле?
но мы вроде же и так перебираем только эти промежутки?
nonedark2008
903 / 642 / 131
Регистрация: 28.07.2012
Сообщений: 1,733
10.04.2013, 22:21 #33
Думаем дальше. Когда у нас B получается >= 2^K ? А тогда, когда X >= 2 ^ K. Т.е. если у нас X >= 2^K, то решений будет 0.
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 22:27  [ТС] #34
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Думаем дальше. Когда у нас B получается >= 2^K ? А тогда, когда X >= 2 ^ K. Т.е. если у нас X >= 2^K, то решений будет 0.
надо что-то с B придумать....
nonedark2008
903 / 642 / 131
Регистрация: 28.07.2012
Сообщений: 1,733
10.04.2013, 22:31 #35
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int main( void )
{
  UINT K = 30, N = 1, M = 2, X = 2 * pow(10, 3);
  UINT A, B;
  UINT num = 0;
  if (M > N)
  {
    swap(A, B);
    swap(M, N);
  }
 
  if (X > (1 << K))
  {
    cout << 0 << endl;
    return 0;
  }
 
  for (A = 0; A < (1 << K); A += N)
  {
    B = A ^ X;
    if (B % M == 0)
      ++num;
  }
  cout << num << endl;
  system("pause");
  return 0;
}
Вот немножко переделал, но наверняка все-равно не пройдет по времени.
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 22:37  [ТС] #36
Цитата Сообщение от nonedark2008 Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int main( void )
{
  UINT K = 30, N = 1, M = 2, X = 2 * pow(10, 3);
  UINT A, B;
  UINT num = 0;
  if (M > N)
  {
    swap(A, B);
    swap(M, N);
  }
 
  if (X > (1 << K))
  {
    cout << 0 << endl;
    return 0;
  }
 
  for (A = 0; A < (1 << K); A += N)
  {
    B = A ^ X;
    if (B % M == 0)
      ++num;
  }
  cout << num << endl;
  system("pause");
  return 0;
}
Вот немножко переделал, но наверняка все-равно не пройдет по времени.
нее, тут вроде мне так кажется оно как было так и останется...(
nonedark2008
903 / 642 / 131
Регистрация: 28.07.2012
Сообщений: 1,733
10.04.2013, 22:41 #37
Цитата Сообщение от yutr777 Посмотреть сообщение
нее, тут вроде мне так кажется оно как было так и останется...(
Остаться то останется, но немножко лучше станет.
lemegeton
2923 / 1352 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
10.04.2013, 22:42 #38
Цитата Сообщение от yutr777 Посмотреть сообщение
нее, тут вроде мне так кажется оно как было так и останется...(
Покажите полностью код, который вы туда сдаете. Есть подозрение, что ваши модификации могут притормаживать.
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 22:45  [ТС] #39
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Остаться то останется, но немножко лучше станет.
ну вот, как я говорил...тоже самое

Добавлено через 1 минуту
Цитата Сообщение от lemegeton Посмотреть сообщение
Покажите полностью код, который вы туда сдаете. Есть подозрение, что ваши модификации могут притормаживать.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
int main()
{
  long long K = 30, N = 1, M = 2, X =0;
  cin >> K >> N >> M >> X;
  long long A, B;
  long long num = 0;
  if (M > N)
  {
    swap(A, B);
    swap(M, N);
  }
 
  if (X > (1 << K))
  {
    cout << 0 << endl;
    return 0;
  }
 
  for (A = 0; A < (1 << K); A += N)
  {
    B = A ^ X;
    if (B % M == 0)
      ++num;
  }
  cout << num << endl;
  return 0;
}
lemegeton
2923 / 1352 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
10.04.2013, 22:49 #40
Как он у вас вообще автотесты проходит? Там же надо что-то считывать со стандартного ввода, выводить на стандартный вывод... А у вас в коде этого нет.
Я что-то не знаю про эту олимпиаду и там дают заранее составленные и известные входные данные?
Тогда
C++
1
std::cout << 4 << std::endl;
ничем не отличается от фактического подсчета.
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 22:51  [ТС] #41
Цитата Сообщение от lemegeton Посмотреть сообщение
Как он у вас вообще автотесты проходит? Там же надо что-то считывать со стандартного ввода, выводить на стандартный вывод... А у вас в коде этого нет.
Я что-то не знаю про эту олимпиаду и там дают заранее составленные и известные входные данные?
Тогда
C++
1
std::cout << 4 << std::endl;
нееет,вы что это просто sample'вские данные в переменные можно обнулить что угондо написать....они все равно потом считываются
lemegeton
2923 / 1352 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
10.04.2013, 22:53 #42
Цитата Сообщение от yutr777 Посмотреть сообщение
нееет,вы что это просто sample'вские данные в переменные можно обнулить что угондо написать....они все равно потом считываются
Тогда еще раз. Покажите, пожалуйста, весь код. Тот самый, который "потом считывает". Есть подозрение, что там тормоза.
nonedark2008
903 / 642 / 131
Регистрация: 28.07.2012
Сообщений: 1,733
10.04.2013, 22:55 #43
Цитата Сообщение от lemegeton Посмотреть сообщение
Тогда еще раз. Покажите, пожалуйста, весь код.
Чувствуется, что на олимпиадах вы не были. Программа тестер сама подает на ввод нужные данные, для этого там и стоит cin.

Добавлено через 46 секунд
Цитата Сообщение от lemegeton Посмотреть сообщение
Есть подозрение, что там тормоза.
Тормоза в том, что при маленьких N совершается огромное число итераций.
lemegeton
2923 / 1352 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
10.04.2013, 22:59 #44
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Чувствуется, что на олимпиадах вы не были. Программа тестер сама подает на ввод нужные данные, для этого там и стоит cin.
То ли лыжи не едут, то ли... я не вижу в этом посте ни одного cin'а.

Добавлено через 45 секунд
Все. Нашел.

Добавлено через 2 минуты
Попробуйте в следующий проход еще убрать лишние библиотеки
C++
1
2
#include <cmath>
#include <algorithm>
Они, конечно, должны аффектить только на этапе компиляции, но кто его знает, что там за система.
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 23:00  [ТС] #45
Цитата Сообщение от lemegeton Посмотреть сообщение
То ли лыжи не едут, то ли... я не вижу в этом посте ни одного cin'а.

Добавлено через 45 секунд
Все. Нашел.

Добавлено через 2 минуты
Попробуйте в следующий проход еще убрать лишние библиотеки
C++
1
2
#include <cmath>
#include <algorithm>
Они, конечно, должны аффектить только на этапе компиляции, но кто его знает, что там за система.
нет, тут решение оптимальнее найти надо(
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.04.2013, 23:00
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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