какое число останется последним

[f1rst]

помогите плз решить задачу
Сичталка
Числа от 1 до n расставлены по кругу. Вычёркиваем каждое второе число, начиная с 1. Нужно составить программу, которая определит, какое число останется последним и напечатает его. Исходное натуральное число-n(1<n<1 000 000).
помгите плз решить

[eoln]

Была похожая задача, но способ не самый оптимальный. Лучше через массив делать. Но может и это подойдёт в качестве "идеи"

type kryg=^person;
person=record
    num:longint;
    Is:boolean;
    nextrec:kryg;
end;
var first,current,last:kryg;
    i,m,MM,n,KOLVO:longint;
BEGIN
    write('N=');readln(n);
    {write('M=');readln(m);}m:=2;//какого вычёркивать
    {MM:=0;}
    MM:=1;//подгоним под условие задачи, чтобы первый вычёркивался
    KOLVO:=n;
    last:=new(kryg);
    first:=last;
    for i:=1 to n do begin//создание и нумерация от 1 до n
        last^.num:=i;
        last^.Is:=true;
        last^.nextrec:=new(kryg);
        last:=last^.nextrec
    end;

    repeat//бесконечный перебор
    current:=first;
        while current<>last do begin
            if current^.Is then begin
               MM:=MM+1;
               if MM>m then MM:=1;
            end;
            if (MM=m)and(current^.Is) then begin
               current^.Is:=false;
               KOLVO:=KOLVO-1;
               {writeln('delete #', current^.num);}
            end;
            if KOLVO=1 then break;
            current:=current^.nextrec;
        end;
    until KOLVO=1;//пока ни останется одно число
        current:=first;
        while current<>last do begin
            if current^.Is then begin
               write('ostalsya #',current^.num);//поиск оставшегося
               readln;
               dispose(last);
               halt;
            end;
            current:=current^.nextrec;
        end;
END.

[f1rst]

спасибо
буду еще больше благодарен если выложите вариант с массивом
заранее спасибо

[puporev]

Алгоритм есть, но проблема с массивом из 1 000 000 элементов.

[alexBlack]

2f1rst Вообще-то это задача Иосифа Флавия. Есть простое рекурентное соотношение. Если это позволяют условия можете воспользоваться им. Описание, например в "Конкретная математика. Основание информатики." Р. Грэхем, Д. Кнут, О. Паташник. Там же сказано, что для миллиона формулы применяются всего 19 раз.