Задача о зубчатой передаче

[tema2434]

Задача о зубчатой передаче

Всем доброго времени суток, подкинули нашей группе такую вот не сложную задачку:
Зубчастая передача состоит из N шестерней, оси оборотов которых находятся на одной прямой. На шестернях нанесены одинаковые метки, которые в начальном состоянии механизма попарно совпадают.Сколько оборотов сделает первая шестерня до того, когда метки на всех шестернях совпадут. Вводим число n - само количество шестерней, дальше через пробел N чисел, x1,x2,xn кол-во зубов каждой шестеренку, вывести через сколько оборотов метки совпадут. Препод дал небольшой пример: Ввод 3 8 15 12 Вывод 15.
Вообщем насколько я верно все понял задача решается с помощью нок, то есть надо из введенных значений, найти найменьшое число которой будет собственно делится на N, в примере это число 15. Собственно как я описал функцию НОК:
Код Pascal

 function Nod(a,b:integer):integer;
begin
  while(a<>0) and (b<>0) do
  if a>=b then a:= a mod b
  else b:= b mod a;
  NOD:=a+b;
  end;
function NOK(a,b:integer):integer;
begin
  NOK:=a*b div NOd(a,b)
  end;

Но как именно осуществить проверку введенных чисел на НОК с первым, думал сделать так:

if (NOK(n,x) < NOK(n,x1)) then Writeln(x);

Но вариантов таких может быть не и не 3, поэтому тут как-раз и стоит вопрос.Я думаю что алгоритм мой верный, надеюсь на вашу помощь, заранее спасибо.

 

[Vladimir_S]

Препод дал небольшой пример: Ввод 3 8 15 12 Вывод 15.

Прежде всего, мне кажется, что Ваш препод дал вам в качестве примера абсолютную чушь. В самом деле, давайте, для начала, решим задачу без всякого программирования.
Итак, есть цепочка из четырех шестерен с числом зубьев 3, 8, 15 и 12. Это значит, что передаточные отношения для шестерен, начиная от второй, по отношению к первой составят (3/8), (3/15) и (3/12) (наличие промежуточных шестерен для третьей и четвертой не имеет значения). Отсюда делаем вывод: если первая шестерня делает N полных оборотов, то прочие сделают (3/8)*N, (3/15)*N и (3/12)*N оборотов, соответственно. В общем случае эти три числа - дробные. Нам же нужно найти такое минимальное N, при котором все четыре шестерни займут исходное положение.
Начнем с того, что найдем требуемое число оборотов (N2, N3 и N4) для каждой из шестерен в отдельности, т.е. если бы были три отдельных сцепки: первая-вторая, первая-третья и первая-четвертая. Эти числа составят 8, 5 и 4, соотвественно. А вот для того, чтобы выполнилось условие возвращения всех шестерен в исходную позицию, необходимо сосчитать наименьшее общее кратное найденных чисел, которое, очевидно, составит 40. Это и будет ответом, а вовсе никакие не 15.

Осталось только написать программу, что я и попробую сделать в свободную минутку.

 

[Vladimir_S]

Ну вот и программа:

Const
 N_gears_max=20;

Type
 Jags=Array[1..N_gears_max] of Integer;

Var
 N_g,i,N_fin:Integer;
 N_j,N_circ:Jags;

Function Number_of_Circles(J1,J2:Integer):Integer;
var
 k,m:Integer;
begin
 k:=0;
 repeat
  Inc(k);
  m:=(J1*k) mod J2;
 until m=0;
 Number_of_Circles:=k;
end;

Function NOK(Ng:Integer; Nc:Jags):Integer;
var
 k,p,Sum:Integer;
begin
 p:=0;
 repeat
  Inc(p);
  Sum:=0;
  for k:=1 to Ng do Sum:=Sum+(p mod Nc[k]);
 until Sum=0;
 NOK:=p;
end;

Begin
 Write('Number of gears = ');
 Readln(N_g);
 for i:=1 to N_g do
  begin
   Write('Number of jags in gear ',i,': ');
   Readln(N_j[i]);
  end;
 Writeln;
 N_circ[1]:=1;
 for i:=2 to N_g do
  N_circ[i]:=Number_of_Circles(N_j[1],N_j[i]);
 N_fin:=NOK(N_g,N_circ);
 Writeln('Number of circles = ',N_fin);
 Readln
End.