Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 21.05.2009, 22:12
гость

 
Сообщений: n/a

НЕ пойму как просще считать выражения вида 8mod3=?
НЕ пойму как просще считать выражения вида 8mod3=?

Непонимаю саму логику такого счета. Есть ли какое нибудь правило как это быстро считать. Помогите разобраться
  #2  
Старый 21.05.2009, 22:33
гость

 
Сообщений: n/a

Это считается как остаток от деления, куда уж проще.
  #3  
Старый 21.05.2009, 22:36
гость

 
Сообщений: n/a

ну и какой остаток от деления 5 mod 3 ??? Как считать то ? Сам принцип??? Не делить же 5 на 3???
  #4  
Старый 21.05.2009, 22:50
гость

 
Сообщений: n/a

5 mod 3 = остаток от деления пяти на три = два.
В школе тебя разве не учили делению в столбик?
  #5  
Старый 21.05.2009, 22:57
гость

 
Сообщений: n/a

сегодня на занятиях люди находили в уме выжражения вида 89 mod 8 , 11571 mod 11 и тому подобное . Быстро без всякого деления в столбик и нахождения остатка. Как они это делали я спросил но не понял аглоритма
  #6  
Старый 21.05.2009, 23:09
гость

 
Сообщений: n/a

89 mod 8 и каждый дурак может сразу посчитать. 88 делится на 8 без остатка, а 89=88+1, отсюда очевидно что остаток равен 1.

А остаток от деления на 11 дейстивтельно можно посчитать в уме очень быстро. Признак деления на 11 тебе когда-нибудь доказывали?
11571 mod 11 = (1*10^4 + 1*10^3 + 5*10^2 + 7*10 + 1) mod 11 = (1 - 1 + 5 - 7 + 1) mod 11 = -1 mod 11 = 10. (здесь мы воспользовались тем фактом что 10^k (mod 11) = 1 если k четно, и -1 если нечетно.)
Т.е. складывай цифры справо налево с попеременным знаком, начинаю с плюса, и посчитатай остаток от деления на 11 получившейся суммы.
На всякий случай, если не знаешь, (-n) mod m = (m - n) mod m.

Цитата:
Быстро без всякого деления в столбик и нахождения остатка. Как они это делали я спросил но не понял аглоритма
Хочешь, приводи сюда их ответ, я тогда тебе его расшифрую.

Но в общем случае деление в столбик самый верный алгоритм. Его несложно и в уме делать если делитель маленький.
  #7  
Старый 21.05.2009, 23:15
гость

 
Сообщений: n/a

Спасибо. Вот это хороший ответ. Уже почти разобрался. Немного потренеруюсь и думаю пойму. Еще раз спс.
  #8  
Старый 21.05.2009, 23:15
гость

 
Сообщений: n/a

Цитата:
Быстро без ... нахождения остатка.
Чушь!
n mod m - это ***ПО ОПРЕДЕЛЕНИЮ*** и есть остаток от делению n на m.
  #9  
Старый 21.05.2009, 23:20
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Чушь!
n mod m - это ***ПО ОПРЕДЕЛЕНИЮ*** и есть остаток от делению n на m.

Я имел ввиду что они не делили в столбик для нахождения остатка, в отличае от меня. Вот поэтому я и спрашивал какой нибудь алгоритм или тому подобное
  #10  
Старый 23.05.2009, 16:08
_persicum_

 
Сообщений: n/a

Давайте немного разгребем и классифицируем то что тут понаписали про нетривиальное взятие остатка, то есть без деления.

1) Если оба операнда (или как их там?) близки, то применяется последовательное вычитание. В сопроцессоре есть даже такая команда, frem. То есть 8 mod 3 = 8 - 3 - 3 = 2

2) Если вычисляется остаток mod 2^n, то деление заменяется на AND (2^n-1).
Например, x mod 8 = x and 7; x mod 256 = x and 255

3) Признаки делимости - будут зависеть от системы счисления!

mod 9 - просто сумма цифр
mod 3 - сумма цифр, из результирующей цифры потом вычитать 3 пока результат не станет меньше 3
mod 7 - последнюю цифру домножаем на 5 и прибавляем.
12345 mod 7 = 1234 + 7*5 = 126 + 9*5 = 17 + 1*5 = 22 = 1 - результат почему-то неправильный, но зато мы знаем, что 12345 не делится на 7 =)))
mod 65537 - младшее слово 16-бит минус старшее 16 бит
mod 1000 - возьми три младших цифры и просто добавь воды!!!

4) Сокращенное деления в столбик без умножения и вычитания!!!
Только сложение заруливает!!!
Попробуем посщитать правильно 12345 mod 7 - таблицы умножения мы не знаем, зато знаем таблиццу остатков:

10 mod 7 = 3
20 mod 7 = 6
30 mod 7 = 2
40 mod 7 = 5
50 mod 7 = 1
60 mod 7 = 4
70 mod 7 = 0
80 mod 7 = 3
90 mod 7 = 6

погнали редуцировать =)))
12345 = 5345 = 445 = 95 = 11 = 4 - Урра!!!

5) И еще много чего интересного, но поля моей мобилки слишком коротки чтобы уместить все это...
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Вывести значение целочисленного выражения, заданного в виде строки S в delphi SergeyHelpMe Математические алгоритмы 5 12.06.2008 12:59
не пойму условия задачи indolent Задачи 2 19.05.2008 07:32
Распознование регулярного выражения Programmer Реализация, исходники, языки 3 29.04.2008 17:23