Отгадать загаданное число

@Maxim35 · Регистрация: 29.05.2016

Author24 — интернет-сервис помощи студентам

Здравствуйте,помогите пожалуйста написать код.Вася загадал число от 1 до N. За какое наименьшее количество вопросов (на которые Вася отвечает "да" или "нет") Петя может угадать Васино число?
Входные данные
Вводится одно число N

Выходные данные
Выведите наименьшее количество вопросов, которого гарантированно хватит Пете, чтобы угадать Васино число.

Примеры
входные данные
5
выходные данные
3

@Peoples · 13.06.2016, 11:08

Решается бинарным(двоичным) поиском с подсчётом итераций

Pascal

const
  size = 1000;
 
type
  am = array[1..SIZE] of integer;
 
var
  a: am; x, m, n, count, first, last: integer; i, j: byte;
  found: boolean;
 
begin
  randomize;
  ReadLn(n);
  for i := 1 to n do
    a[i] := i;
  
  m :=random(n-1+1)+1;
  
  for i := 2 to n do                         
    for j := n downto i do                    
      if a[j - 1] > a[j] then begin
        x := a[j - 1];
        a[j - 1] := a[j];
        a[j] := x;
      end;     
  count := 0;
  First := 1;
  Last := n;
  Found := False; 
  
  repeat 
    i := (First + Last) div 2; 
    if a[i] = m then Found := True
    else
    begin
      if a[i] > m then First := i + 1 
      else Last := i - 1; 
    end;
    count := count + 1; 
  until (Found) or (First > Last);  
if Found then
else 
  Writeln('Поиск выполнен за ', count);
end.

@кот Бегемот · 13.06.2016, 11:27

Peoples, всё гораздо проще.

Pascal

var
n,m,k:integer;
begin
readln(n);
k:=0;
m:=1;
while m<n do
begin
m:=m*2;
inc(k);
end;
writeln(k);
end.

@Alex1603 · 04.08.2019, 16:35

кот Бегемот, Почему нужно умножать на 2?

@~~Pvt~~ · 04.08.2019, 18:57

ну можно (n:=n div 2)>0

@кот Бегемот · 04.08.2019, 20:20

кот Бегемот, Почему нужно умножать на 2?

Потому что за 1 правильный вопрос мы сокращаем количество оставшихся чисел в два раза, пока не останется одно. Умножая единицу на 2 мы идём в обратную сторону, пока не придём к исходному количеству чисел.

@JuriiMW · 05.08.2019, 03:59

Можно ещё сократить число переменных:

Pascal

var n, c : Integer;
begin
  Read(n);
  c := 0;
  while n > 0 do
    begin
      n := n shr 1;
      inc(c);
    end;
  Write(c);
end.

@кот Бегемот · 05.08.2019, 16:04

JuriiMW, к сожалению, ваша программа неверна.

@Gerfest · 18.04.2020, 18:28

Ответ одной строкой - это log₂(n), округлённый в большую сторону.

@agvego5 · 21.12.2023, 18:47

Сообщение от JuriiMW

Можно ещё сократить число переменных:

да. до нуля.

Pascal

1 2	### print(1+trunc(log(ri)/log(2)));

Добавлено через 3 минуты

Сообщение от кот Бегемот

Peoples, всё гораздо проще.

намного

@Cyborg Drone · 21.12.2023, 21:49

agvego5, здесь общий раздел паскаля, а не раздел Pascal ABC.NET. Будьте внимательнее.

@Maxim35 0 / 0 / 0 Регистрация: 29.05.2016 Сообщений: 27
		1
	Отгадать загаданное число 12.06.2016, 21:35. Показов 19711. Ответов 10 Метки нет (Все метки) Здравствуйте,помогите пожалуйста написать код.Вася загадал число от 1 до N. За какое наименьшее количество вопросов (на которые Вася отвечает "да" или "нет") Петя может угадать Васино число? Входные данные Вводится одно число N Выходные данные Выведите наименьшее количество вопросов, которого гарантированно хватит Пете, чтобы угадать Васино число. Примеры входные данные 5 выходные данные 3 0

@Alex1603 0 / 0 / 0 Регистрация: 10.03.2019 Сообщений: 16
	04.08.2019, 16:35	4
	кот Бегемот, Почему нужно умножать на 2? 0

@~~Pvt~~ Заблокирован
	04.08.2019, 18:57	5
	ну можно `(n:=n div 2)>0` 0

@кот Бегемот Платежеспособный зверь 8926 / 4354 / 1642 Регистрация: 28.10.2009 Сообщений: 11,568
	04.08.2019, 20:20	6
	кот Бегемот, Почему нужно умножать на 2? Потому что за 1 правильный вопрос мы сокращаем количество оставшихся чисел в два раза, пока не останется одно. Умножая единицу на 2 мы идём в обратную сторону, пока не придём к исходному количеству чисел. 0

@кот Бегемот Платежеспособный зверь 8926 / 4354 / 1642 Регистрация: 28.10.2009 Сообщений: 11,568
	05.08.2019, 16:04	8
	JuriiMW, к сожалению, ваша программа неверна. 0

@Gerfest 0 / 0 / 0 Регистрация: 18.04.2020 Сообщений: 1
	18.04.2020, 18:28	9
	Ответ одной строкой - это log₂(n), округлённый в большую сторону. 0

@Cyborg Drone Модератор 9855 / 5225 / 3304 Регистрация: 17.08.2012 Сообщений: 15,986
	21.12.2023, 21:49	11
	agvego5, здесь общий раздел паскаля, а не раздел Pascal ABC.NET. Будьте внимательнее. 0

Опции темы

Отгадать загаданное число

Решение