Объсните решение!Вырубка деревьев.Паскаль.Задача перебор!

[suppppper2007]

Задача Паскаль вырубка деревьев
Король Флатландии решил вырубить некоторые деревья, растущие перед его дворцом. Деревья перед дворцом короля посажены в ряд, всего там растет N деревьев, расстояния между соседними деревьями одинаковы.

После вырубки перед дворцом должно остаться M деревьев, и расстояния между соседними деревьями должны быть одинаковыми. Помогите королю выяснить, сколько существует способов вырубки деревьев.

Требуется написать программу, которая по заданным числам N и M определит, сколько существует способов вырубки некоторых из N деревьев так, чтобы после вырубки осталось M деревьев и соседние деревья находились на равном расстоянии друг от друга.

Входные данные

Входной файл INPUT.TXT содержит два целых числа M и N (0 Ј M, N Ј 1000).

Выходные данные

В выходном файле OUTPUT.TXT должно содержаться одно число - искомое количество способов.Пример INPUT.TXT: OUTPUT.TXT для примера:
5 3 4

Ограничение времени: 1 сек на тест

РЕШЕНИЕ

program trees;
var
n, m : longint;

i, d, s : longint;
input_file, output_file : Text;

begin
Assign(input_file,'INPUT.TXT');
Assign(output_file,'OUTPUT.TXT');
Reset(input_file);
ReWrite(output_file);
ReadLn(input_file,n,m);
Close(input_file);

s := 0;
if m = 0 then s := 1
else if m = 1 then s := n
else for d := 1 to (n-1) div (m-1) do Inc(s,n-(m-1)*d);

Write(output_file,s);
Close(output_file);
end.

Объясните решение плиз,вот эту строку вообще не понимаю else for d := 1 to (n-1) div (m-1) do Inc(s,n-(m-1)*d);
неясно что мы обозначаем переменной д что такое н-1 див м-1 про инк и далее вообще не понятно что там делается

короче говоря нужен разбор этой задачи..объясните ничего не понимаю смысл сам решения не понимаю...откуда берётся этот н-1 див м-1 и что это такое..почему мы увеличиваем с именно на n-(m-1)* д ХЭЛППП!!!:confu sed:

[Utkin]

Else - ложная ветвь условия. d - это счетчик шагов в цикле. То есть d принимает значение с каждым шагом от 1 до (n-1) div (m-1)
(n-1) и (m-1) скорее всего от того, что это того что нумерация начинается от нуля (хотя здесь может быть и другой прикол)
div - деление нацело. Нельзя использовать (n-1) / (m-1) поскольку результат получится дробным (точнее может получиться), а это не есть хорошо поскольку d может принимать только целые значения (в свою очередь это связано с тем, что это переменная цикла - а она всегда целое число, без всяких запятых). Инк - это операция сложения к s c каждым шагом прибавляется n-(m-1)*d.
Почему именно это выражение? Наверно это задано условием задачи:
там растет N деревьев, расстояния между соседними деревьями одинаковы.

После вырубки перед дворцом должно остаться M деревьев, и расстояния между соседними деревьями должны быть одинаковыми.

Всего деревьев N каждый раз рубим М (здесь каждый раз и есть d)

Вообще это наглядный образец отвратительного почерка. Отсутствие комментариев и куча вложений на одной строке может запутать кого угодно. В общем здесь показано как оформлять не надо.

[puporev]

(n-1) и (m-1) это количество промежутков в начале и в конце, их всегда на 1 меньше чем точек.

[suppppper2007]

Сообщение от Utkin

Else - ложная ветвь условия. d - это счетчик шагов в цикле. То есть d принимает значение с каждым шагом от 1 до (n-1) div (m-1)
(n-1) и (m-1) скорее всего от того, что это того что нумерация начинается от нуля (хотя здесь может быть и другой прикол)
div - деление нацело. Нельзя использовать (n-1) / (m-1) поскольку результат получится дробным (точнее может получиться), а это не есть хорошо поскольку d может принимать только целые значения (в свою очередь это связано с тем, что это переменная цикла - а она всегда целое число, без всяких запятых). Инк - это операция сложения к s c каждым шагом прибавляется n-(m-1)*d.
Почему именно это выражение? Наверно это задано условием задачи:
там растет N деревьев, расстояния между соседними деревьями одинаковы.

После вырубки перед дворцом должно остаться M деревьев, и расстояния между соседними деревьями должны быть одинаковыми.

Всего деревьев N каждый раз рубим М (здесь каждый раз и есть d)


Вообще это наглядный образец отвратительного почерка. Отсутствие комментариев и куча вложений на одной строке может запутать кого угодно. В общем здесь показано как оформлять не надо.

А разве мы рубим не Н-М ??

[puporev]

А разве мы рубим не Н-М ??

При чем здесь это? Нам надо не сколько рубим, а количество вариантов. Это задача на комбинаторику. Чтоб понять откуда что берется, порешайте вручную при небольших N, например при N=7 и просмотрите все варианты М от 1 до 7. Вы сами увидите последовательность, которую Вам и выразили формулой.

Может так понятнее будет. В принципе количество вариантов считается как сумма членов арифметической прогрессии, у которой первый член равен 1, а количество членов и шаг зависят от N и M, как это написано в приведенном варианте, просто решение из цикла переходит в линейный алгоритм. Пример без файла, просто так тестировать быстрее.

program trees;
uses crt;
var
n, m ,k: longint;
i, d, s : longint;
begin
clrscr;
write('n=');readln(n);
write('m=');readln(m);
s := 0;{сумма прогрессии}
k:=(n-1) div (m-1);{количество членов прогрессии}
d:=m-1;{шаг прогрессии}
s:=(2+(k-1)*d)*k div 2;{формула суммы первых членов арифметической прогрессии}
write(s);
readln;
end.

Кстати без цикла должно быстрее работать. У меня при значениях 1000 и 2 программа работает доли секунды, почти мнгновенно.

[suppppper2007]

Краткие комментарии по решению задач и системе тестов

Задача A. Вырубка деревьев

Зафиксируем расстояние между деревьями после вырубки. Если оно равно d, то возможно
n – d(m – 1) – m + 1 способов вырубить деревья. Суммируя по всем d, получаем ответ.

вот такую вот инфу нашла..

получается d*(m-1) это количество промежутков после вырубки равных определённому расстоянию д а что такое тогда н-м+1??

[puporev]

Вы так никогда не разберетесь с задачей, поскольку итоговые формулы порлучаются в результате преобразований и на первый взгляд не имеют смысла. Пока Вы не разберетесь с алгоритмом на бумаге сами, вряд ли возможно его Вам объяснить заочно, ибо это и просто и сложно одновременно. Это надо ПОНЯТЬ. Кстати, если будете использовать мой код не забудьте вставить проверки из Вашего кода, я просто написал как цикл заменить на линейный алгоритм.

program trees;
uses crt;
var
n, m ,k: longint;
i, d, s : longint;
begin
clrscr;
write('n=');readln(n);
write('m=');readln(m);
if m=0 then s:=1
else if m=1 then s:=n
else
 begin
  k:=(n-1) div (m-1);{количествао членов прогрессии}
  d:=m-1;{шаг прогрессии}
  s:=(2+(k-1)*d)*k div 2;{формула суммы первых членов арифметической прогрессии}
 end;
write(s);
readln;
end.

[suppppper2007]

я разобрала на бумаге при н=7 и м от 1 до 7 и из этого поняла

Сообщение от suppppper2007

Краткие комментарии по решению задач и системе тестов

получается d*(m-1) это количество промежутков после вырубки равных определённому расстоянию д а что такое тогда н-м+1??

а меня теперь очень интересует в результате каких преобразований получается вот эта итоговая формула s=s+(n-(m-1)*d)