Для перебора возможных выражений использовал обратную польскую нотацию.
Получается всего 5 возможных шаблонов расположений операций и операндов. Если символом '0' обозначить операнды, а символом '1' — операции, эти 5 шаблонов будут выглядеть так:
0 0 1 0 1 0 1
0 0 1 0 0 1 1
0 0 0 1 1 0 1
0 0 0 1 0 1 1
0 0 0 0 1 1 1
Каждый из них можно закодировать одним числом. Для удобства младшим битом будем считать крайний левый. Тогда получится пятерка { 84, 100, 88, 104, 112 }. Еще нужно заметить, что в любом выражении ровно четыре операнда и ровно три операции.
Остается перебрать все четверки цифр a < b < c < d, для каждой из них рассмотреть все их перестановки (24 штуки), все 5 шаблонов и все возможные варианты подстановки операций (3 позиции для операций * 4 возможных операции = 12 вариантов), и для каждой такой комбинации вычислить значение выражения.
Решение не учитывает коммутативности операций, но и так работает примерно за секунду.
Сигма — это не математическая сумма и не большая буква Е.
Сигма — это буква греческого алфавита, если Вы не знали. То, что у Вас на рисунке — именно большая буква сигма, и ничто иное.
int main()
{
int fact[10];
fact[0] = 1;
for (int i = 1; i < 10; ++i)
fact[i] = i * fact[i — 1];
int a = 0;
int x = 1000000 — 1;
for (int i = 9; i >= 0; --i)
{
int d = x / fact[i];
int j = 0;
for (int k = 0;; ++j)
if (0 == (a & (1 << j)))
if (k++ == d) break;
a |= (1 << j);
std:: cout << j;
x -= d * fact[i];
}
}
Первая задача решается без кода. Достаточно найти суммы арифметических прогрессий A = 3 + 6 +… + 999 (числа, делящиеся на 3), B = 5 + 10 +… + 995 (числа, делящиеся на 5), C = 15 + 30 +… + 990 (числа, делящиеся на 15) и вычислить выражение A+B-C. :)
А во второй можно найти несколько интересных рекуррентных соотношений. Сначала для удобства допишем к последовательности Фибоначчи слева единицу: тогда четные члены будут иметь номера, делящиеся на 3. Обозначим последовательность Фибоначчи за a[n], а за b[n] подпоследовательность четных членов: b[n] = a[3 * n]. Тогда нам нужно для некоторого N найти сумму S[N] = b[1] + b[2] + b[3] +… + b[N]. Можно заметить и доказать соотношение b[n+2] = b[n] + 4 * b[n+1]. На этом, в принципе, можно остановиться — просто просуммировать b[n] в цикле. Но также можно заметить, что S[n] = (b[n] + b[n+1] — 2) / 4, и тогда можно вычислять последовательность b[n], ничего не суммируя по ходу. Короче, решение на языке калькулятора bc:
Кстати об устройствах, содержащих в себе инструкцию в электронном виде: например, некоторые факсы умеют распечатывать страницы со справкой. :) Может быть и принтеры тоже, но я не встречал.
Кнопками < и > я тоже не пользуюсь, если они маленькие. Если же это ссылки с надписью "далее"/"следующая страница" и т. п., то пользуюсь по ним проще попасть мышкой :)
Выше в таких красочных деталях описывают, какой же это кайф бросить курить, что я прямо-таки уже начал жалеть, что не курю и что, соответственно, мне нечего бросать :)
Простите, если повторил чью-то мысль не осилил нцать страниц комментариев.
Получается всего 5 возможных шаблонов расположений операций и операндов. Если символом '0' обозначить операнды, а символом '1' — операции, эти 5 шаблонов будут выглядеть так:
0 0 1 0 1 0 1
0 0 1 0 0 1 1
0 0 0 1 1 0 1
0 0 0 1 0 1 1
0 0 0 0 1 1 1
Каждый из них можно закодировать одним числом. Для удобства младшим битом будем считать крайний левый. Тогда получится пятерка { 84, 100, 88, 104, 112 }. Еще нужно заметить, что в любом выражении ровно четыре операнда и ровно три операции.
Остается перебрать все четверки цифр a < b < c < d, для каждой из них рассмотреть все их перестановки (24 штуки), все 5 шаблонов и все возможные варианты подстановки операций (3 позиции для операций * 4 возможных операции = 12 вариантов), и для каждой такой комбинации вычислить значение выражения.
Решение не учитывает коммутативности операций, но и так работает примерно за секунду.
clipie.org/view.php? key=9S2WJDHN0VL5M6Z4KXYQ
Сигма — это буква греческого алфавита, если Вы не знали. То, что у Вас на рисунке — именно большая буква сигма, и ничто иное.
#include <iostream>
int main()
{
int fact[10];
fact[0] = 1;
for (int i = 1; i < 10; ++i)
fact[i] = i * fact[i — 1];
int a = 0;
int x = 1000000 — 1;
for (int i = 9; i >= 0; --i)
{
int d = x / fact[i];
int j = 0;
for (int k = 0;; ++j)
if (0 == (a & (1 << j)))
if (k++ == d) break;
a |= (1 << j);
std:: cout << j;
x -= d * fact[i];
}
}
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
int main()
{
int v[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
for (int i = 1; i < 1000000; ++i)
next_permutation(v, v + 10);
copy(v, v + 10, ostream_iterator<int>(cout));
}
Брутфорс на Руби:
a = {}
(2..100).each{ |i| (2..100).each { |j| a[i ** j] = 1 } }
puts a.length
Тем не менее, код на С++: clipie.org/view.php? key=E1ZLSOPRG7M4UCK30FIT
А во второй можно найти несколько интересных рекуррентных соотношений. Сначала для удобства допишем к последовательности Фибоначчи слева единицу: тогда четные члены будут иметь номера, делящиеся на 3. Обозначим последовательность Фибоначчи за a[n], а за b[n] подпоследовательность четных членов: b[n] = a[3 * n]. Тогда нам нужно для некоторого N найти сумму S[N] = b[1] + b[2] + b[3] +… + b[N]. Можно заметить и доказать соотношение b[n+2] = b[n] + 4 * b[n+1]. На этом, в принципе, можно остановиться — просто просуммировать b[n] в цикле. Но также можно заметить, что S[n] = (b[n] + b[n+1] — 2) / 4, и тогда можно вычислять последовательность b[n], ничего не суммируя по ходу. Короче, решение на языке калькулятора bc:
a = 0
b = 2
while (b < 4000000)
{
c = a + 4 * b
a = b
b = c
}
print (a + b — 2) / 4
quit
Хотел поделиться своим решением второй задачи, а там не разрешают его запостить, пишут Thread Locked (Archived).
Тут пару месяцев назад обсуждали:
http://habrahabr.ru/blog/typography/39566.html
Простите, если повторил чью-то мысль не осилил нцать страниц комментариев.