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

🟢 23:40 Відбій повітряної тривоги
  • Автор теми Автор теми Murder
  • Дата створення Дата створення

Murder

Статус: Офлайн
Реєстрація: 17.06.2007
Повідом.: 53
Помогите решить задачку на pascal

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

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

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

Ты хочешь, чтобы тебе программу написали или тебе нужен алгоритм? Идеи есть?
 
Останнє редагування:
AposTol сказав(ла):
По-моему для этого достаточно школьных знаний по паскалю...

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

мне бы хоть что нибуть, идей вобще нету мне дали 3 задачи 2 легко сделал а на этой застрял :confused:
 
Останнє редагування:
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.

А в чём собсно проблема?
Или я чё-то не понил?
 
Останнє редагування:
2 sefiroth: у Вас количество чисел (переменная "c") в 2 раза больше получится, т.к. Вы сравниваете, к примеру, и тройку с шестеркой, и шестерку с тройкой (чуть позже), а ведь пара то одна ... А вообще, тут, имхо, вообще циклы перебора использовать ни к чему, достаточно просто формулку вывести ...
 
fatalex сказав(ла):
2 sefiroth: у Вас количество чисел (переменная "c") в 2 раза больше получится, т.к. Вы сравниваете, к примеру, и тройку с шестеркой, и шестерку с тройкой (чуть позже), а ведь пара то одна ... А вообще, тут, имхо, вообще циклы перебора использовать ни к чему, достаточно просто формулку вывести ...
Натисніть, щоб розгорнути...
С чего бы это? Он когда в первом цикле проходит 6, во втором к 3 уже не возвращается.
 
я тут 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

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

Вроде так ...
 
Останнє редагування:
понятно, что "понятнее и полегче" :)

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

но коль задачку задавали как по программингу на Паскале, причем попросили показать ход расчета - очевидно на это решение (Sefiroth) и рассчитывали ... пользуйся ... тока вот чего ... ты в условиях оговорил, что нужно найти количество чисел, у Sefiroth'а сейчас, имхо, считается количество пар, а не чисел. Понял? Удачи ...
 
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 поделить на константу - не получится никак.
 
Останнє редагування:
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. Т.е. задача или шуточная или некорректно сформулирован вопрос ... Нас ведь не просят узнать кол-во подобных чисел в каждой группе. Просто - сколько всего ...
 
Останнє редагування:
Во-первых, можно и без "Вы", ибо я студЭнт и учусь на 2 курсе. )))

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

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