Форум программистов
 
Расширенный поиск
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

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

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

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

Добрый день.
Помогите собрать код для такой задачи.
Условие: В последовательности натуральных чисел от 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, 13:11   #2
Serge_Bliznykov
МегаМодератор
СуперМодератор
 
Регистрация: 09.01.2008
Сообщений: 23,156
Репутация: 5118
По умолчанию

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

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

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

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

Код:

  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 в 14:32.
Аватар вне форума   Ответить с цитированием
Старый 08.02.2018, 14:43   #5
Serge_Bliznykov
МегаМодератор
СуперМодератор
 
Регистрация: 09.01.2008
Сообщений: 23,156
Репутация: 5118
По умолчанию

Цитата:
Сообщение от 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, 15:08   #6
kim-im
Пользователь
 
Регистрация: 07.11.2017
Сообщений: 20
Репутация: 10
По умолчанию

Спасибо. Вы мне очень помогли.
Код в принципе работает. И я уже в нете нашёл такую же задачу.
Действительно число останется максимальная степень 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, 15:09   #7
kim-im
Пользователь
 
Регистрация: 07.11.2017
Сообщений: 20
Репутация: 10
По умолчанию

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

Код:

var
  n: int64;
begin
  Read(n);
  Write(1 shl Trunc(log2(n)));
end.

Не помню есть в TP log2
__________________
Если ничто другое не помогает, прочтите, наконец, инструкцию! Аксиома Кана
Plague вне форума   Ответить с цитированием
Ответ



Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

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




06:12.


Powered by vBulletin® Version 3.8.8 Beta 2
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

купить трафик


как улучшить посещаемость, а также решения по монетизации сайтов, видео и приложений

RusProfile.ru


Справочник российских юридических лиц и организаций.
лучший хостинг
Выбираем лучший хостинг: рейтинг ТОП 10
Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru