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

Раскраска таблицы умножения - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Работа с неструктурированными данными http://www.cyberforum.ru/cpp-beginners/thread1154904.html
Для исследования различных методов доступа к файлам данных необходимо выполнить следующие подготовительные действия: 1) Создать в Блокноте следующий текстовый файл input_1.txt: У меня спросили:...
C++ B zero идентификатор не найден Приветствую всех, столкнулся с необходимостью использовать bzero(). Вот такой код не работает. Тут http://www.opennet.ru/docs/RUS/libc/libc-4.html сказано подключать #include <string.h>. Однако... http://www.cyberforum.ru/cpp-beginners/thread1154895.html
C++ Как открыть проект в программе, не запуская саму программу
Ребят, такая тема: У меня есть программа, в которой я создаю проекты, но как сделать так, что бы при запуске созданного мной проекта 1) Запускалась моя программа, можно ли сделать программно, что...
Переполнение при расчете функции C++
рассчитываю функцию, получается переполнение, что делается в таких случаях? // raschet # include <iostream.h> # include <conio.h> # include <math.h> long double x(int k,long double...
C++ Не выполняется условие сравнения строк с номером телефона http://www.cyberforum.ru/cpp-beginners/thread1154871.html
Вот программа через структуру, ввод данных: Фамилия Имя, дата рождения, номер телефона. Когда вводит в запросе номер телефон он должен выдавать всю информацию о человеке с которым совпал номер...
C++ Вычислить площадь простого многоугольника В первой строке вводится одно число N (3≤N≤100000). Далее в N строках задается по паре чисел – координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки. ... подробнее

Показать сообщение отдельно
TrueBit
95 / 95 / 12
Регистрация: 19.11.2012
Сообщений: 195
29.04.2014, 22:54
Цитата Сообщение от Live4Sky Посмотреть сообщение
у меня с множествами туговато.
Цитата Сообщение от ValeryS Посмотреть сообщение
но по моему решать циклами такое глупо
нужно как то комбинаторику сюда приладить
пока не могу сказать как
Если через комбинаторику, то задача связана с множествами и формулой включения-исключения. Вот что получилось:

теория:
Кликните здесь для просмотра всего текста
Выведем нужные формулы, а также рассмотрим их на примере таблицы 10*10:

1 2 3 4 5 6 7 8 9 10
2 4 6 8 10 12 14 16 18 20
3 6 9 12 15 18 21 24 27 30
4 8 12 16 20 24 28 32 36 40
5 10 15 20 25 30 35 40 45 50
6 12 18 24 30 36 42 48 54 60
7 14 21 28 35 42 49 56 63 70
8 16 24 32 40 48 56 64 72 80
9 18 27 36 45 54 63 72 81 90
10 20 30 40 50 60 70 80 90 100


ВВЕДЕМ ОБОЗНАЧЕНИЯ:
n = общее число строк
m = общее число столбцов
r,g,b - конечные множества
r = c/2 = число_чисел_делящихся_на_2
g = c/3 = число_чисел_делящихся_на_3
b = c/5 = число_чисел_делящихся_на_5
rAg=r^g = c/(2 ^ 3) = число_чисел_делящихся_на_2_и_3
rAb=r^b = c/(2 ^ 5) = число_чисел_делящихся_на_2_и_5
gAb=g^b = c/(3 ^ 5) = число_чисел_делящихся_на_3_и_5
rVg = c/(2 V 3) = число_чисел_делящихся_на_2_или_3
rVb = c/(2 V 5) = число_чисел_делящихся_на_2_или_5
gVb = c/(3 V 5) = число_чисел_делящихся_на_3_или_5
r^g^b = c/(2 ^ 3 ^ 5) = чило_чисел_делящихся_на_3_и_5_и_7
r^g^b = c/(2 ^ 3 ^ 5) = чило_чисел_делящихся_на_3_или_5_или_7
строки\столбцы будем называть просто рядами

rVgVb = r + g + b - (r^g + r^b + g^b) + r^g^b - формуля включения-исключения для 3х множеств

рассмотрим формулы для случая n=10, m=10
формулы, приведенные ранее(набор формул 1)
r = c/2 = число_нужных_столбцов*n + число_нужных_строк*m - пересечения_нужных_рядов = (m/2)*n + (n/2)*m - (n/2)*(m/2) = 50+50-25 = 75
g = c/3 = число_нужных_столбцов*n + число_нужных_строк*m - пересечения_нужных_рядов = (m/3)*n + (n/3)*m - (n/3)*(m/3) = 30+30-9 = 51
b = c/5 = число_нужных_столбцов*n + число_нужных_строк*m - пересечения_нужных_рядов = (m/5)*n + (n/5)*m - (n/5)*(m/5) = 20+20-4 = 36

аналогичные, для объединений цветов(набор формул 2):
rVg = c/(2 V 3) = число_нужных_столбцов*n + число_нужных_строк*m - пересечения_нужных_рядов = (m/2 + m/3 - m/(2*3))*n + (n/2 + n/3 - n/(2*3))*m - (n/2 + n/3 - n/(2*3))*(m/2 + m/3 - m/(2*3)) = 91
rVb = c/(2 V 5) = число_нужных_столбцов*n + число_нужных_строк*m - пересечения_нужных_рядов = (m/2 + m/5 - m/(2*5))*n + (n/2 + n/5 - n/(2*5))*m - (n/2 + n/5 - n/(2*5))*(m/2 + m/5 - m/(2*5)) = 84
gVb = c/(3 V 5) = число_нужных_столбцов*n + число_нужных_строк*m - пересечения_нужных_рядов = (m/3 + m/5 - m/(3*5))*n + (n/3 + n/5 - n/(3*5))*m - (n/3 + n/5 - n/(3*5))*(m/3 + m/5 - m/(3*5)) = 75
rVgVb = c/(2 V 3 V 5) = число_нужных_столбцов*n + число_нужных_строк*m - пересечения_нужных_рядов = (m/2 + m/3 + m/5 - m/(2*3) - m/(2*5) - m/(3*5) + m/(2*3*5))*n + (n/2 + n/3 + n/5 - n/(2*3) - n/(2*5) - n/(3*5) + n/(2*3*5))*m - (n/2 + n/3 + n/5 - n/(2*3) - n/(2*5) - n/(3*5) + n/(2*3*5))*(m/2 + m/3 + m/5 - m/(2*3) - m/(2*5) - m/(3*5) + m/(2*3*5)) = 96

вспоминая математику, имеем, мощность объединения двух множеств есть сумма мощностей этих множеств за вычетом их объединения, aVb = a + b - a^b
отсюда a^b = a + b - aVb
применительно к нашим множествам(набор формул 3):
r^g = r + g - rVg = 75 + 51 - 91 = 35
r^b = r + b - rVb = 75 + 36 - 84 = 27
g^b = g + b - gVb = 51 + 36 - 75 = 12

из формулы включения-исключения
rVgVb = r + g + b - (r^g + r^b + g^b) + r^g^b
находим
r^g^b = rVgVb + (r^g + r^b + g^b) - (r + g + b) = 96 + (35 + 27 + 12) -(75 + 51 + 36) = 8

итак, нашли все что нам нужно

теперь находим цвета:

в синий красим последний поэтому, число синих чисел не зависит от покраски в другие цвета:
BLUE : b = 36
зеленый красим перед синим, поэтому из числа зеленых чисел вычитаем те которые красились в оба цвета зеленый+синий
GREEN : g - g^b = 51 - 27 = 39
красный красим перед зеленым и синим, поэтому из числа красных чисел вычитаем число чисел которые помимо красного красились в синий и зеленый(они перекрасили) и добавляем пересечение(если вычли 2 раза, тоесть число во все цвета красили)
RED : r - r^g - r^b + r^g^b = 75 - 35 - 27 + 8 = 21

чтобы найти число чисел окрашеных в черный цвет, найдем общее число чисел и вычтим число чисел которые окрашены хотябы в 1 цвет, тоесть вычтем мощность объединения множеств из общей мощности множества чисел таблицы т.е.

BLACK : n*m - rVgVb = 10*10 - 96

окончательно имеем:
RED : 21
GREEN : 39
BLUE : 36
BLACK : 4


решение на c++:
Кликните здесь для просмотра всего текста
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
34
#include<iostream>
#include<fstream>
using namespace std;
 
int main() {
    //ifstream cin("input.txt");
    //ofstream cout("output.txt");
    int n=0,m=0;
    int r=0,g=0,b=0;
    int rAg=0,rAb=0,gAb=0;
    int rVg=0,rVb=0,gVb=0;
    int rAgAb=0,rVgVb=0;
 
    cin >> n >> m;
 
    r=(m/2)*n + (n/2)*m - (n/2)*(m/2);
    g=(m/3)*n + (n/3)*m - (n/3)*(m/3);
    b=(m/5)*n + (n/5)*m - (n/5)*(m/5);
 
    rVg=(m/2 + m/3 - m/(2*3))*n + (n/2 + n/3 - n/(2*3))*m - (n/2 + n/3 - n/(2*3))*(m/2 + m/3 - m/(2*3));
    rVb=(m/2 + m/5 - m/(2*5))*n + (n/2 + n/5 - n/(2*5))*m - (n/2 + n/5 - n/(2*5))*(m/2 + m/5 - m/(2*5));
    gVb=(m/3 + m/5 - m/(3*5))*n + (n/3 + n/5 - n/(3*5))*m - (n/3 + n/5 - n/(3*5))*(m/3 + m/5 - m/(3*5));
    rAg= r + g - rVg;
    rAb= r + b - rVb;
    gAb= g + b - gVb;
 
    rVgVb = (m/2 + m/3 + m/5 - m/(2*3) - m/(2*5) - m/(3*5) + m/(2*3*5))*n + (n/2 + n/3 + n/5 - n/(2*3) - n/(2*5) - n/(3*5) + n/(2*3*5))*m - (n/2 + n/3 + n/5 - n/(2*3) - n/(2*5) - n/(3*5) + n/(2*3*5))*(m/2 + m/3 + m/5 - m/(2*3) - m/(2*5) - m/(3*5) + m/(2*3*5));
    rAgAb = rVgVb + (rAg + rAb + gAb) - (r + g +b);
 
    cout << "RED" <<" "<<":"<< " " << r - rAg - rAb + rAgAb << endl;
    cout << "GREEN" << " " << ":" << " " << g - gAb << endl;
    cout << "BLUE" << " " << ":" << " " << b << endl;
    cout << "BLACK" <<" "<<":"<< " " << n*m - rVgVb << endl;
}
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru