Просмотр полной версии : Делимость на семь
Nadir Zaitov
12.01.2010, 16:00
Эта задачка на программирование была на реальной республиканской олимпиаде по программированию в далеком 1990-м году. Предлагаю решить устным описанием алгоритма. (Напомнил мне ее Руслан в задаче про вино и рабов).
Есть очень большое действительное число, выраженное в двоичной системе.
Нужно определить остаток от деления на число семь (7).
Тетстовое число было типа:
110110......500 раз "10"....1100101001011B
Каменный век, а... Юзаем либу GMP, mpz_mod(), профит...
Nadir Zaitov
12.01.2010, 16:43
Каменный век, а... Юзаем либу GMP, mpz_mod(), профит... А разрядности там хватает? Речь идет о 2-3 миллионах знаках, например... и о скорости. Нужно оптимизировать решение (найти быстрый алгоритм вычисления такого остатка)!
Эта задачка на программирование была на реальной республиканской олимпиаде по программированию в далеком 1990-м году. Предлагаю решить устным описанием алгоритма. (Напомнил мне ее Руслан в задаче про вино и рабов).
Есть очень большое действительное число, выраженное в двоичной системе.
Нужно определить остаток от деления на число семь (7).
Тетстовое число было типа:
110110......500 раз "10"....1100101001011B
Поскольку число 7 в двоичном представлении выглядит 111, то следует разделить заданное число от конца на триады и выполнить суммирование троек цифр. Если число делится на 7, то полученная сумма будет делиться на 7.
Для данного числа: последние цифры в сумме 1110.
Далее следуют 1000 цифр, то есть 1 цифра "лишняя" для тройки.
Поэтому сумма первых цифр:"110110(00)" будет 110.
Сумма "переда" и "зада" = 10100.
Теперь суммируем "группы-500".
101010- такая группа безусловно делится на7.
500:3 (по 3 раза) = 166 (ОСТАТОК 2 ГРУППЫ)
Прибавим: 1010+10100=11110.Таким образом, число 11100 делится на 7, а вот 10(в двоичном виде)- остаток. То есть остаток равен 2.:biggrin:
Rooslan Khayrov
12.01.2010, 16:51
Блин, элементарная задача, но я полчаса тупил. Арифметика по модулю. Вычисляем значение числа слева направо в соответствии с определением двоичной системы, всё по модулю 7.
Т.е. начинаем со старшего разряда и на N-м шаге берём результат предыдущего шага, умножаем на два, прибавляем значение текущего разряда и берём остаток от деления результата на 7.
А у меня так... начинаем с права на лево...:) 1ую, 4ую, 7ую... итд... единички складываем... прибавляем к этому числу 2ую, 5ую, 8ую... итд. единички помноженные на 2; прибавляем 3ю 6ую, 9 ую... итд... единички помноженные на 4; и делим на 7 полученное число...:) -получаем остаток:)
Nadir Zaitov
12.01.2010, 17:09
Поскольку число 7 в двоичном представлении выглядит 111, то следует разделить заданное число от конца на триады и выполнить суммирование троек цифр. Если число делится на 7, то полученная сумма будет делиться на 7. Ну... так не интересно. Вы знали отгадку. Это "самое простое решение" на олимпиаде 1989 год (как оказалось) из ташкентских парней почти никто нормально не решил.
Nadir Zaitov
12.01.2010, 17:47
Вот еще задача из указанной серии.
Вы наверное знаете отрезки Кантора.
На первом этапе у нас есть начальный отрезок [0,1], из него мы вырезаем центральную треть и получаем отрезоки второго этапа:
На втором этапе у нас есть отрезоки [0;1/3] и [2/3;1], из них мы опять выкидываем средние кусочки.
На третьем этапе у нас есть 4 отрезка и т.д.
Кстати, это у нас в пределе получается множества мощностью континиума но с нулевой мерой. Т.е. точек в этом множестве столько же, сколько в отрезке от 0 до 1, а длинна всего множества "отрезков" будет равна нулю :)
Так вот, дано некоторое число А из интервала (0,1). Определить, является ли оно числом Кантора (входит во все отрезки всех этапов) или определить этап, на котором это число вылетает из множества кантора этого этапа.
Так вот, дано некоторое число А из интервала (0,1). Определить, является ли оно числом Кантора (входит во все отрезки всех этапов) или определить этап, на котором это число вылетает из множества кантора этого этапа. кошмар!!!
Shuhrat Ismailov
19.01.2010, 13:36
Вот еще задача из указанной серии.
На первом этапе у нас есть начальный отрезок [0,1], из него мы вырезаем центральную треть и получаем отрезоки второго этапа:
На втором этапе у нас есть отрезоки [0;1/3] и [2/3;1], из них мы опять выкидываем средние кусочки.
На третьем этапе у нас есть 4 отрезка и т.д.
Так вот, дано некоторое число А из интервала (0,1). Определить, является ли оно числом Кантора (входит во все отрезки всех этапов) или определить этап, на котором это число вылетает из множества кантора этого этапа.
На первом шаге мы вырезали (1/3, 2/3). Троичное разложение точки А из этого обязательно содержит цифру 1 на первой позиции, т.е. x = 0,1........ Аналогично на втором шаге мы вырезали интервалы (1/9, 2/9) и (7/9, 8/9). Троичное разложение чисел из этих интервалов обязательно содержит цифру 1 на второй позиции 0,01..... или 0,21....... Шагая таким образом до бесконечности, получаем следующее:
а) число А является числом Кантора тогда и только тогда, когда его можно представить троичной дробью, используя лишь цифры 0 и 2.
б) Если в троичном разложении числа А цифра 1 встречается впервые на i - той позиции, то она выкинута i - том этапе.
Nadir Zaitov
19.01.2010, 21:06
Точно. Задачка была на систему исчисления... кстати, крайние точки отрезка взодят в множество Кантора. Т.е. число 0,2 в троичной системе входит в множество Кантора.
Тепеь нужен алгоритм. Дано число A/B (A<B). Лежит ли в множестве Кантора? Т.е. задача получить мантису и период разложения числа в троичной системе.
Shuhrat Ismailov
20.01.2010, 10:22
число 0,2 в троичной системе входит в множество Кантора.
Тепеь нужен алгоритм. Дано число A/B (A<B). Лежит ли в множестве Кантора? Т.е. задача получить мантису и период разложения числа в троичной системе.
Нужно также иметь в виду, что число 0,1=0,0(2) тоже канторово
Пока еще здесь алгоритмов не выложили -написала программку которая должна решать эту задачу...:) -не обольщайтесь ее скромным размером -если она у вас не работает... то вам нужно скачать вот это
(http://www.microsoft.com/downloads/details.aspx?FamilyID=d0e5dea7-ac26-4ad7-b68c-fe5076bba986&DisplayLang=ru) размером в 200мб:biggrin:
Nadir Zaitov
21.01.2010, 16:54
написала программку которая должна решать эту задачу... Уже начала программировать? Молодцом, но лучше выписать код или описать алгоритм словами.
Ildar Valiev
21.01.2010, 17:39
если она у вас не работает... то вам нужно скачать вот это
размером в 200мб
Зачем для такой программы Framework 3.5? O_O
Уже начала программировать? Молодцом, но лучше выписать код или описать алгоритм словами.
Ага, прошла курсы, а то у нас в Университете, к сожалению, этому не обучают...:( -получила сертификат...:)https://img.uforum.uz/images/joiaasp1902159.gif
перепишу код:
public static bool IsKantor(int a, int b)
{
if (a > b) throw new Exception("А не должно быть больше В");
if (b == 0) throw new DivideByZeroException();
List<int> MyList = new List<int>();
MyList.Add(a);
int i = 0;
do
{
i++;
if (a == 0) return true;
if ((a >= b) && (a < b * 2))
{
if ((a - b) == 0) return true;
else return false;
}
if (a >= b * 2)
{
a = a - 2 * b;
foreach (int item in MyList)
{
if (item == a) return true;
}
MyList.Add(a);
}
a = a * 3;
} while ((MyList.Count<10000)&&(i<1000000));
throw new Exception("Не получается посчитать");
}
Собственно в основе лежит вариант Схемы Горнера (http://ru.wikipedia.org/wiki/%D0%A1%D1%85%D0%B5%D0%BC%D0%B0_%D0%93%D0%BE%D1%80% D0%BD%D0%B5%D1%80%D0%B0)...:)
Зачем для такой программы Framework 3.5? O_O К сожалению умею только на с#...
vBulletin® v3.8.5, Copyright ©2000-2025, Jelsoft Enterprises Ltd. Перевод: zCarot