воскресенье, 29 января 2012 г.

Играем в игру и участвуем в конкурсе.

Наталия Макарова, исследователь магических квадратов, рассказала мне о конкурсе математиков-программистов. Но, чтобы принять в нём участие и, возможно, даже выиграть, программистом быть необязательно, достаточно иметь развитое логическое мышление.

В конкурсе предлагается пройти 25 уровней классической компьютерной игры Same Game. Вам всем, наверняка, встречалась подобная игровая механика. С поля, заполненного квадратиками разных цветов нужно убирать группы в 2 или более смежных квадратов одного цвета.

На сайте конкурса можно скачать программу с заданиями, там же работает и форма приёма решений.
Игроки ранжируются по количеству набранных очков. Убрав группу из n квадратов вы получаете (n-1)2 баллов. Если вам удастся полностью очистить поле, то вы получите бонус, равный h*w*c/2, где h - высота поля, w - ширина, c - количество цветов.

Чтобы скопировать своё решение для отправки выбирайте Move - Solution to Clipboard.

Удачи! Вам решать, кто же победит в конкурсе - перебирающий миллионы комбинаций алгоритм или человеческая интуиция.

вторник, 24 января 2012 г.

Деление на 10... уголком!

При решении задачи на нахождение пропущенных цифр в числе 34! один участник олимпиады, зачем-то, начал делить это число на 10. Делил он уголком.

Кстати, а какие же цифры должны быть на месте точек и как их на самом деле нужно находить?

среда, 18 января 2012 г.

Ещё способ

Ещё один простой способ генерации кода Грея связан со следующим процессом:

Начинаем с буквы А. Далее поступаем по следующем правилу: приписываем справа следующую букву, а после неё - повторяем все ранее записанные символы. После первого шага получим строку
АВА
После второго: АВАСАВА
После третьего:
АВАСАВАDАВАСАВА

Теперь возьмём двоичное число 0000 и обозначим его цифры как DCBA. Пробежимся по строке и будем менять на противоположную ту цифру, которая соответствует текущему символу в строке:
А: 0001
В: 0011
А: 0010
С: 0110
А: 0111
В: 0101
А: 0100
D: 1100
А: 1101
В: 1111
А: 1110
С: 1010
А: 1011
В: 1001
А: 1000

Как отметил наш читатель Вадим, есть ещё один рекурсивный способ: сначала получаем код Грея длины 3, записываем его сначала в прямом порядке, а потом в обратном. И дописываем перед первой половиной 0, а перед второй — 1.

вторник, 17 января 2012 г.

Код Грея

Рассмотрим все возможные комбинации из трёх цифр: нулей или единиц. Обычно из записывают в таком порядке:
000
001
010
011
100
101
110
111

То есть в виде двоичных представлений числе от 0 до 7. Однако эти 8 строки можно записать и так, чтобы каждая пара соседних элементов отличалась только одним символом:
000
001
011
010
110
111
101
100

Такое упорядочивание называется кодом Грея. Заметим, что первая срока от последней также отличается ровно одним символом.

Можно ли подобное сделать для шестнадцати строк от 0000 до 1111? Да, и вот какой способ формирования 4-битного кода Грея показал мне Кузнецов Сергей Тихонович.

Обозначим 4 двоичных цифры буквами A, B, C, D. А каждое из 16 чисел будет представлено ячейкой вот в такой таблице:

Если ячейка находится в колонке (строке), отмеченной буквой, в соответствующем разряде числа будет стоять единица. Иначе - ноль.

При такой разметке таблицы числа, стоящие в соседних ячейках, будут отличаться только одним разрядом. Поэтому код Грея можно сформировать, обойдя все ячейки, например, так:
Этот путь даст нам последовательность:
1100
1110
0110
0100
0101
0001
0000
0010
0011
0111
1111
1011
1010
1000
1001
1101

Её тоже можно зациклить и начинать с любого элемента.

пятница, 13 января 2012 г.

Фокус параболы

Парабола определяется как геометрическое место точек, для которых расстояние до данной прямой равно расстоянию до данной точки.

парабола как геометрическое место точек
Эта прямая называется директрисой параболы, а точка - её фокусом.

воскресенье, 8 января 2012 г.

Вектория

Уже неделя нового года, а я ничего сюда не написал. Как вы можете догадаться, работаю над новой игрой :) Но по мотивам старой цитаты с баша родилась тема для поста

xxx: купила рыбку, назвала Вектория
yyy: ВИктория
xxx: нет, Вектория
yyy: почему??
xxx: потому что скалярия :)

Игра слов здесь в том, что величина может быть скалярной или векторной. Скалярные величины не имеют направления. Это, например, масса, сумма денег на счету, электрический заряд. Для других величин направление существенно, они называются векторными. Это скорость, сила, ускорение. Любая векторная величина имеет соответствующую ей скалярную, равную модулю этого вектора.

Популярные сообщения

Темы

число цифра простые геометрия юмор дроби язык степень делимость пи методы история квадрат самоописывающее время задача система счисления узор корень тригонометрия структура е сайты конструкция формулы игра факториал функции приближение программа фрактал комбинаторика последовательность график память логарифм вероятность палиндром пределы конкурс треугольник магический квадрат неизвестное правильно-неправильное действие видео интеграл уравнение комплексные софизм заблуждения процесс ряды цитаты книги окружность прогрессия среднее стереометрия число фи выражения графы матрица проценты разрезания логика парабола символ статистика 2014 Фибоначчи клеточный автомат кривая производная фокус головоломка действия иллюзия куб шахматы многоугольник новости оказывается оригами подобие построение сложение термин тетраэдр топология