Помогите решить задачку на pascal

Murder · 02.02.2008

Помогите решить задачку на pascal

вот условие задачи :

Посчитайте сколько чисел в первой сотне сравнимы друг с другом по модулю 3 (имеют один и тот же остаток от деления на три) Выведите получение числа на экран

помогите очень буду благодарен

...:::Alex:::... · 02.02.2008

пипец...

AposTol · 03.02.2008

По-моему для этого достаточно школьных знаний по паскалю...

Ты хочешь, чтобы тебе программу написали или тебе нужен алгоритм? Идеи есть?

Murder · 03.02.2008

AposTol сказав(ла):
По-моему для этого достаточно школьных знаний по паскалю...

Ты хочешь, чтобы тебе программу написали или тебе нужен алгоритм? Идеи есть?

мне бы хоть что нибуть, идей вобще нету мне дали 3 задачи 2 легко сделал а на этой застрял :confused:

Sefiroth · 03.02.2008

var i,j,c:integer;
begin
c:=0;
for i:=1 to 100 do
for j:=i to 100 do
if (i mod 3)=(j mod 3) then
begin
writeln('Числа ',i,' и ',j,' сравнимы по модулю 3');
c:=c+1;
end;
end.

А в чём собсно проблема?
Или я чё-то не понил?

AposTol · 03.02.2008

Sefiroth, ну а "c" вывести?

Murder · 03.02.2008

Sefiroth, Спасибо

VaDRo · 03.02.2008

я бы искал как минимум по j от i + 1. Как-нибудь так

Sefiroth · 03.02.2008

VaDRo сказав(ла):
я бы искал как минимум по j от i + 1. Как-нибудь так

Нупочему же...
Ведь число сравнимо само с собой по модулю 3... По крайней мере с утра было...

VaDRo · 03.02.2008

ИМХО, Это понятно и ежу

И по идее таки стоило бы исключить надписи в кол-ве 100 штук о том, что число сравнимо само с собой

AposTol · 04.02.2008

ИМХО, Это понятно и ежу И по идее таки стоило бы исключить надписи в кол-ве 100 штук о том, что число сравнимо само с собой

Ежу-то понятно, но надо посчитать =)

fatalex · 04.02.2008

2 sefiroth: у Вас количество чисел (переменная "c") в 2 раза больше получится, т.к. Вы сравниваете, к примеру, и тройку с шестеркой, и шестерку с тройкой (чуть позже), а ведь пара то одна ... А вообще, тут, имхо, вообще циклы перебора использовать ни к чему, достаточно просто формулку вывести ...

Das Zugunfall · 04.02.2008

fatalex сказав(ла):
2 sefiroth: у Вас количество чисел (переменная "c") в 2 раза больше получится, т.к. Вы сравниваете, к примеру, и тройку с шестеркой, и шестерку с тройкой (чуть позже), а ведь пара то одна ... А вообще, тут, имхо, вообще циклы перебора использовать ни к чему, достаточно просто формулку вывести ...

С чего бы это? Он когда в первом цикле проходит 6, во втором к 3 уже не возвращается.

fatalex · 04.02.2008

ой, мля ... беру свои слова назад ...
"for j:=i to 100 do" прочитал как "for j:=1 to 100 do" ...
сорри ...

fatalex · 04.02.2008

я тут 2-мя постами назад тормознул, сорри ...

предлагаю другое решение задачки для условий:
пусть М=100 (100 первых числе ОТ "1"), n=3 (делитель), обозначим С[i, j] - количество сочетаний из i по j без повторений - считается как i!/(j!*(i-j)!), i! - факториал от "i".

Следующий код (изменено так, чтобы считать РАЗНЫЕ числа, сравнимые по модулю n):
for i:=1 to M-1 do for j:=i+1 to M do if (i mod n)=(j mod n) then c:=c+2; // +2, т.к. пару образуют 2 числа

заменяем на формулу:
c = C[M div n, 2]*2*3 + (M mod n)*(M div n)*2

Имеем тоже самое без перебора, только надо предусмотреть расчет больших факториалов, или упростить его ...

Вроде так ...

Murder · 06.02.2008

Помоему код Sefiroth будет попонятнее и полегче

fatalex · 06.02.2008

понятно, что "понятнее и полегче"

просто это скорее математическая задачка и решать ее должно формулкой, а не перебором, пусть и не полным ... Дело в том, что при увеличении числа M (до которого нужно считать) время расчета будет расти весьма быстрее роста числа M. А для формулки - что до 100, что до 10000000 - похрену ...

но коль задачку задавали как по программингу на Паскале, причем попросили показать ход расчета - очевидно на это решение (Sefiroth) и рассчитывали ... пользуйся ... тока вот чего ... ты в условиях оговорил, что нужно найти количество чисел, у Sefiroth'а сейчас, имхо, считается количество пар, а не чисел. Понял? Удачи ...

Sefiroth · 06.02.2008

fatalex, да, твой код будет работать не на много быстрей, если ваще будет. Оба алгоритма будут в общем случае иметь сложность ~M^2.
Щас изложу свою точку зрения.

Мозьмём твоё же M = 10 000 000

10 000 000 факториал - это число из примерно 5 000 000 десятичных цифр, или 25 000 000 двоичных (бит) - чуть больше 8 Мб.

Во-первых прийдётся организовать работу с такими числами.
Во-вторых, самый оптимальный алгоритм умножения, который мне пришёл в голову - это умножение двоичным деревом, где сложность вычисления конечного факториала будет равна опять же M^2 / 2, как и сложность моего алгоритма.

Т.е. вместо перебора чисел в цикле ты перебираешь их при вычислении факториала. )))

ЗЫ: Думаю, тут ваще ничё крутого нельзя придумать в общем случае - разве что оптимизировать для частного.
Ведь порядок результата возрастает экспоненциально по отношению к порядку входного результата (например входному результату длиной в 7 десятичных знаков будет соответствовать выходной результат длиной примерно 10^7 / 2 знаков). Поэтому, думаю, сделать эту задачу проще чем M^2 поделить на константу - не получится никак.

fatalex · 07.02.2008

2 sefiroth:
Чтобы посчитать отношение 5!/3! необязательно считать (1*2*3*4*5)/(1*2*3). Как Вы можете заметить реально надо посчитать всего то 4*5.

Посему в моем примере циклов нет вообще ни явных, ни скрытых (даже при вычислении факториалов) и обработку больших чисел надо вводить действительно при больших числах.

Сложность Вашего кода M*(M-1)! , если я не ошибаюсь ...

Насчет работы моего кода - до опубликования я тупо загнал в Ексель эти формулки и проверил соответствие с Вашим кодом. Правда, есть небольшие изменения в условиях, в своем посте я их привел ...

PS Я по работе довольно часто сталкиваюсь с необходимостью переборов, включая полный, стараюсь, где можно, этого избегать ...

Еще, по моему мы спорим ни о чем - перечитал еще раз условие задачи.

Посчитайте сколько чисел из M первых сравнимы друг с другом по модулю n

Вдумайтесь, не сколько РАЗНЫХ пар, ни сколько чисел, составляющих РАЗНЫЕ пары, просто - сколько чисел ...
Дык если считать, что 3 и 3 - подходят, к примеру, то таких чисел всегда M. И пофигу M - первых, или начиная с двойки, с тройки ...

Пример: M=5 n=2

Числа 1, 3, 5 - первый сет; 2 и 4 - второй сет. Сколько всего чисел? 5. Т.е. задача или шуточная или некорректно сформулирован вопрос ... Нас ведь не просят узнать кол-во подобных чисел в каждой группе. Просто - сколько всего ...

Sefiroth · 07.02.2008

Во-первых, можно и без "Вы", ибо я студЭнт и учусь на 2 курсе. )))

Сложность моего кода M^2, т.к. количество проходов будет увеличиваться пропорционально M^2, а в каждом проходе будет выполняться задача, порядок сложности которой ноль, ибо от M или шага прохода цикла она не зависит.

А на счёт неправильного условия - а где, простите, щас в школе можно найти нормального препода по информатике, который хотя бы подбирает реальные жизненные задачи, и знает хотя бы не меньше своих учеников? )))
Лично я такого, к сожалению, не видел.