Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 08.02.2018, 11:18   #1
kim-im
Пользователь
 
Регистрация: 07.11.2017
Сообщений: 42
По умолчанию Одно число

Добрый день.
Помогите собрать код для такой задачи.
Условие: В последовательности натуральных чисел от 1 до N сначала вычеркнули все нечетные, потом те, что стояли на нечетных местах в т.д., пока осталось только одно число. Какое это число?
Входные данные: Натуральное число N(от 2 до 2 в степени 63)
Исходные данные: Число, что останется.
Задача как бы несложная. Если заметить, то здесь всего два цикла, которые повторяются: 1-ый-удаляет нечётные элементы, 2-ой-элементы, стоящие на нечётных местах.
Я не могу собрать код для этой задачи так, что бы он работал.
Помогите пожалуйста.
Код для нечётных:
Код:
for i:= 1 to n do
   begin
    if odd (a[i]) then
      write(a[i], ' ');
   end;
Код для стоящих на нечётных местах:
Код:
for i:= 1 to n do
   begin
    if odd (i) then
      write(a[i], ' ');
   end;
kim-im вне форума Ответить с цитированием
Старый 08.02.2018, 12:11   #2
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от kim-im Посмотреть сообщение
Если заметить, то здесь всего два цикла, которые повторяются
если обратить внимание, что в начале нечётные числа стоят на нечётных местах, то очевидно, что достаточно ОДНОГО цикла.

а вообще, это известная задача, см. "Задача Иосифа Флавия или считалка Джозефуса"

Последний раз редактировалось Serge_Bliznykov; 08.02.2018 в 12:13.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 08.02.2018, 13:00   #3
Black Fregat
Программист
Участник клуба
 
Аватар для Black Fregat
 
Регистрация: 23.06.2009
Сообщений: 1,772
По умолчанию

Зачем циклы? При такой постановке задачи останется максимальная степень двойки, входящая в набор.
Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
Задача Иосифа Флавия
Насколько я понял, это другая задача. Тут нет кольца
Black Fregat вне форума Ответить с цитированием
Старый 08.02.2018, 13:23   #4
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Код:
  i:=1;
  while N>1 do begin i:=i*2; N:=N div 2; end;
  write(i);
и не нужно ни чего вычеркивать ))

Найти такое k, что бы 2^k <= N < 2^(k+1)
То 2^k и останется после вычеркиваний
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

Последний раз редактировалось Аватар; 08.02.2018 в 13:32.
Аватар вне форума Ответить с цитированием
Старый 08.02.2018, 13:43   #5
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от Black Fregat Посмотреть сообщение
Насколько я понял, это другая задача. Тут нет кольца
согласен.
просто очень похожая.


Цитата:
Сообщение от Black Fregat Посмотреть сообщение
Зачем циклы? При такой постановке задачи останется максимальная степень двойки, входящая в набор.
Гениально!!!

подтверждение (https://ideone.com/1HbAE7) (с "вычёркиваниями"):
Код:
program ideone;

var a: array of integer;
  i, n, k, prev : integer;
  
  procedure PrintA; var i:integer;
  begin
    for i:=1 to n do
      if a[i]>0 then Write(a[i],' ');
    writeLn
  end;  
  
begin
  repeat
    n := 33;
  until n>0;  
  if n=1 then WriteLn(1)
  else begin
    SetLength(a,n+1);
    for i:=1 to n do a[i]:=i; PrintA;
    repeat
      k:=0;
      prev := 1;
      for i:=1 to n do 
       if a[i]>0 then begin
         Inc(k);
         if prev>0 then begin a[i] := 0; prev := 0 end
         else inc(prev);
       end; 
      PrintA;
    until k=1;
    SetLength(a,0);
  end;
end.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 08.02.2018, 14:08   #6
kim-im
Пользователь
 
Регистрация: 07.11.2017
Сообщений: 42
По умолчанию

Спасибо. Вы мне очень помогли.
Код в принципе работает. И я уже в нете нашёл такую же задачу.
Действительно число останется максимальная степень 2.
Но код проходит на 95%.
Что нужно ещё учесть?. Спасибо
Код:
var i,n:integer;
begin
read(n);
i:=1;
  while N>1 do 
    begin
     i:=i*2; 
     N:=N div 2; 
    end;
  write(i);
end.
kim-im вне форума Ответить с цитированием
Старый 08.02.2018, 14:09   #7
kim-im
Пользователь
 
Регистрация: 07.11.2017
Сообщений: 42
По умолчанию

Кстати тип я поставил int64 вместо integer
kim-im вне форума Ответить с цитированием
Старый 16.02.2018, 22:25   #8
Plague
Забанен
Форумчанин Подтвердите свой е-майл
 
Аватар для Plague
 
Регистрация: 01.11.2006
Сообщений: 420
По умолчанию

Код:
var
  n: int64;
begin
  Read(n);
  Write(1 shl Trunc(log2(n)));
end.
Не помню есть в TP log2
Если ничто другое не помогает, прочтите, наконец, инструкцию! Аксиома Кана
Plague вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Из заданных чисел рандомно выбрать одно число FleXik Общие вопросы Delphi 11 15.10.2013 03:43
Умножение на одно число m837 Microsoft Office Excel 1 18.05.2011 20:35
Как объединить цифры в одно число? y.barninets Паскаль, Turbo Pascal, PascalABC.NET 4 11.12.2010 19:09
За один ход можна вычеркнуть одно число и на его место записать строго меньше неотрицательное число. Witaliy Помощь студентам 5 25.02.2009 17:44
Можно ли разделить сразу несколько цифр на одно и тоже число? Xell Microsoft Office Excel 2 12.01.2009 13:32