Задача: Найти N-ный элемент последовательности Хемминга
Стыдно сказать, но о том, что последовательность простых чисел, расположенных по возрастанию, называется последовательностью Хемминга, я узнала буквально вчера, когда искала какую-нибудь интересную типовую задачу для сайта. О простых числах, которые считаются простыми, потому что делятся только на себя и на единицу, мне естественно известно со школы, но вот бедный Хемминг и его последовательность... А может, просто забылась эта смешная фамилия за давностью лет... Так или иначе, создался повод поговорить о решении заданий на последовательность Хемминга. К примеру, требуется написать программу на Delphi, которая из введенных пользователем 4 чисел (вид [2 3 5 N]), извлекает N и находит N-ный элемент последовательности. Что касается алгоритма, задача у нас состоит из двух частей - для начала требуется выделить нужный нам признак N, а уж затем искать его в последовательности, которую предварительно нужно как-то сформировать. На мой взгляд, наибольно сложная часть алгоритма состоит в том, чтобы именно сформировать последовательность Хемминга. И сформировывать ее я решила в динамическом массиве, потому что заранее размерность массива в принципе не известна и ограничена этим самым N. К сожалению, заполнение массива мне представляется ни чем иным как перебором всех чисел, расположенных до искомого. Поэтому используем цикл while do. Нужные нам числа из последовательности будем определять по булевому флагу AddBool, который будет принимать значение False, в случае, если текущая выборка делится еще на какое-либо простое число из нашего массива, помимо себя и единицы. В общем, все описанные задачи выглядят следующими Delphi исходниками:
procedure TForm1.Button1Click(Sender: TObject); var s:string; i, number:integer; nEl:integer; arrHemm: array of integer; AddBool:boolean; nAdd: integer; begin s:=Edit1.text;
number:=2; ArrHemm[0]:=1; ArrHemm[1]:=2; nAdd:=2; AddBool:=true; while ArrHemm[nEL-1]=0 do begin number:=number+1; for i := 1 to nEl-2 do if ArrHemm[i]<>0 then if Number mod ArrHemm[i]=0 then AddBool:=false; if addBool=true then begin ArrHemm[nAdd]:=number; nAdd:=nAdd+1 end; AddBool:=true; end; edit1.Text:=intTostr(ArrHemm[nEL-1]) end;
end; Как вы видите, первые 2 числа последовательности Хемминга я задала самостоятельно для удобства. Переменная nAdd по сути является адресом для вставки в массив нового простого числа, и она равна 2, поскольку это индекс следующего числа, после заданных мной. Увеличиваем его вручную, потому как не каждый цикл будет соответствовать его увеличению. Все неизвестные ячейки массива принимаются равными нулю, поэтому необходимо это учитывать. Задача решена:) Возможно ваше задание несколько отличается от представленного и вызывает у вас какие-либо трудности - напишите мне - я выполню решение на заказ.
