Точная степень двойки как найти

7  Модуль. Цикл while

Цикл while («пока»)
— это так называемый цикл с условием или с предусловием. В цикле for мы
явно указываем, какие значения будет принимать переменная i,
например, 1 <= i <= 10.
В цикле while можно задавать более
сложные условия, например, i ** 2 <= 10,
кроме того можно использовать логические операции «И»,
«ИЛИ» и т.д.

Цикл while позволяет
выполнить одну и ту же последовательность действий, пока проверяемое условие
истинно. Условие записывается до тела цикла и проверяется до выполнения тела
цикла. Как правило, цикл while используется,
когда невозможно определить точное значение количества проходов исполнения
цикла.

Синтаксис цикла while в
простейшем случае выглядит так:

while
условие:

    блок инструкций

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

Пример:

Следующий фрагмент программы
напечатает на экран всех целые числа, не превосходящие n, и их сумму:

s = 0

i = 1

while i <= n:

    print(i)

    s +=
i

    i +=
1

Пример:

C предыдущей задачей, однако,
мог бы справиться и цикл for .
Рассмотрим более сложную задачу, с которой for уже
не справится: вывести на экран все степени двойки, не превосходящие 100.
Её также удобно решать с помощью цикла while.

i =
1

while
i <= 100:

    print(i)

    i *=
2

После окончания цикла
значение i будет уже больше, чем 100, иначе цикл бы продолжился.
Последнее напечатанное значение будет соответственно равно 64.

Пример:

Немного изменим задачу:
найдём максимальную степень двойки, не превосходящую 100.

p =
1

while
p * 2 <=
100:

    p *=
2

print(p)

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

Пример:

Вот еще один пример
использования цикла while для
определения количества цифр натурального числа n и их суммы:

s = 0

n = int(input())

count = 0

while n > 0:

    count += 1

    s += n %
10

    n //= 10

print(count)

print(s)

В этом цикле мы отбрасываем
по одной цифре числа, начиная с конца, что эквивалентно целочисленному делению
на 10  (n //= 10),
при этом считаем в переменной count, сколько раз это было сделано, а в
переменной s — сумму отброшенных цифр.

Задачи.

Трискайдекафобия

Трискайдекафобия — боязнь
числа 13. В особо сложных формах пациент боится и всех чисел,
кратных 13.

Дано число N. Выведите
все целые числа по возрастанию, начиная с числа N, пока не встретится
число, кратное 13. Его выводить не нужно.

Входные данные

Дано натуральное число N, не
превосходящее 10000.

Выходные данные

Выведите ответ на задачу.

Примечание

Программа должна быть решена при помощи
одного цикла while,
без if внутри цикла.

   

Решение.

Номер числа Фибоначчи

Последовательность Фибоначчи
определяется так:

ϕ₀=0, ϕ₁=1,
ϕ_n=ϕ_n−1+ϕ_n−2

Дано натуральное
число A. Определите, каким по счету числом Фибоначчи оно является, то есть
выведите такое число n, что ϕ_n=A. Если A не
является числом Фибоначчи, выведите число −1.

Входные данные

Вводится натуральное
число A (2≤A≤2∗10⁹).

Выходные данные

Выведите ответ на задачу.

 

Точная степень двойки

Дано натуральное число N. Выведите
слово YES, если число N является точной степенью двойки, или слово NO
в противном случае.

Операцией возведения в степень пользоваться нельзя!

Входные
данные

Вводится
натуральное число, не превосходящее 200.

Выходные
данные

Выведите
ответ на задачу.

Банковские проценты

Вклад в банке составляет x рублей.
Ежегодно он увеличивается на p процентов, после чего дробная часть от копеек отбрасывается.
Определите, через сколько лет вклад составит не менее y рублей. В
задаче запрещено использовать дробные числа.

Входные данные

Программа получает на вход три натуральных числа: x, p, y (x≤2000,p≤100,y≤2000).

Выходные данные

Программа должна вывести одно целое число — ответ на
задачу.

Примечание

Обратите внимание, что вклад в банке измеряется в рублях,
а отбрасывается дробная часть копеек.

Решение

Минимальный простой делитель

Дано целое число, не меньшее 2. Выведите его
наименьший простой делитель.

Входные
данные

Вводится
целое положительное число N≤2∗10⁹.

Выходные
данные

Выведите
ответ на задачу.

Решение

 

Список квадратов

По данному целому числу N распечатайте
все квадраты натуральных чисел, не превосходящие N, в порядке
возрастания.

Входные
данные

Вводится
натуральное число, не превосходящее 100.

Выходные
данные

Выведите
ответ на задачу.

Решение

Обработка последовательностей
неизвестной длины.

 

С помощью цикла for мы могли решать задачи, обрабатывающие
последовательности числовых данных, например, посчитать сумму или произведение
элементов некоторой последовательности с известным числом элементов.

Однако бывают случаи, когда заранее неизвестно
число элементов последовательности, а ввод ограничен тем или иным образом. С
использованием цикла while можно решать задачи для этого случая. Рассмотрим
пример такой задачи.

Пример:

Дана последовательность натуральных чисел,
заканчивающаяся нулем. Требуется найти произведение и количество этих чисел
(ноль не должен участвовать в нахождении произведения).

Решение
может выглядеть так:

count = 0

prod = 1

elem = int(input())

while elem != 0:

    count += 1

    prod *= elem

    elem = int(input())

print(prod)

print(count)

Рассмотрим
более сложную задачу.

Пример:

Дана последовательность неизвестной длины,
требуется вывести первое число, которое встречается два раза подряд. Гарантируется,
что такое число существует.

Для решения задачи потребуется хранить не только
текущее считанное значение, но и предыдущее:

prev = int(input())

elem = int(input())

while elem != prev:

    prev = elem

    elem = int(input())

print(elem)

Второй минимум

Последовательность состоит из натуральных чисел и
завершается числом 0. Определите значение второго минимального по
величине элемента в этой последовательности, то есть элемента, который будет
наименьшим, если из последовательности удалить наименьший элемент.

Последнее число 0 не
учитывается. Гарантируется, что в последовательности есть хотя бы два элемента
(кроме завершающего числа 0).

Входные
данные

На вход подаётся последовательность целых неотрицательных
чисел, заканчивающаяся нулём. Все числа в последовательности неотрицательные,
по значению не превосходящие 10⁹.

Выходные
данные

Выведите
ответ на задачу.

Решение

Количество элементов, которые больше предыдущего

 

Последовательность состоит из натуральных чисел и
завершается числом 0. Определите, сколько элементов этой
последовательности больше предыдущего элемента.

Входные
данные

Вводится последовательность натуральных чисел,
оканчивающаяся числом 0 (само число 0 в
последовательность не входит, а служит как признак её окончания).

Выходные
данные

Выведите ответ на задачу.

Решение

 

Количество локальных максимумов

Элемент последовательности называется строгим
локальным максимумом, если он строго больше предыдущего и последующего
элементов последовательности. Первый и последний элемент последовательности не
являются локальными максимумами.

Входные
данные

Дана
последовательность натуральных чисел, завершающаяся числом 0.
Гарантируется, что все числа не превосходят 100.

Выходные
данные

Определите
количество строгих локальных максимумов в этой последовательности.

Решение

Среднее значение последовательности

Определите среднее значение всех элементов
последовательности, завершающейся числом 0. Сам ноль в
последовательность не входит.

Использовать массивы в данной задаче нельзя.

Входные данные

Вводится последовательность целых чисел, оканчивающаяся
числом 0 (само число 0 в
последовательность не входит, а служит как признак её окончания).

Выходные данные

Выведите ответ на задачу.

Решение

 

Самое частое число в последовательности

Последовательность состоит из натуральных чисел,
причем  какое-то из чисел составляет более половины от общего числа членов
последовательности. Найдите это число.

Для решения этой задачи запрещено использование массивов
и списков.

Входные данные

На вход подается последовательность натуральных чисел, заканчивающаяся
нулём. Его обрабатывать не нужно. Гарантируется, что все числа не
превосходят 10⁹.

Выходные данные

Выведите ответ на задачу.

Решение

Нам дана последовательность
чисел и известно, что одно из чисел встречается в последовательности более
половины раз. Это число требуется найти.

Воспользуемся следующим
свойством. Если из этой последовательности мы выкинем два различных элемента,
то искомое число по прежнему будет встречаться более половины раз.
Действительно, так как мы выкидываем два различных числа, то максимум один
экземпляр искомого числа будет выкинут и как минимум одно число, не являющееся
искомым, будет выкинуто, поэтому искомое число будет как и прежде встречаться
более половины раз.

Используем это свойство. Будем
запоминать, какое число ans встречалось нам чаще всех и
количество count таких появлений этого числа. Если
счетчик count равен 0, то мы обновляем
переменную ans и увеличиваем счетчик на 1. Если мы встречаем
число, записанное в переменной ans, то мы будем увеличивать счетчик
на 1, в противном случае будем уменьшать его на 1. Каждому уменьшению
счетчика на 1 соответствует увеличение счетчика на 1, которое
было произведено ранее, и такая пара операций равносильна удалению двух разных
чисел из последовательности. Следовательно, по свойству описанному выше, такой
алгоритм найдет нам искомое число и оно будет записано в переменной ans.

Решение:

ans = 0

count
= 0

elem
= int(input())

while
elem != 0:

    if
count == 0:

       
ans = elem

       
count += 1

    elif
elem == ans:

       
count += 1

    else:

       
count —= 1

   
elem = int(input())

print(ans)

Выдача сдачи

Имеется неограниченное количество монет в 1, 2, 5, 10 рублей.
Определите, сколькими способами можно выдать сдачу в n рублей. Например, 5 рублей
можно выдать четырьмя способами: 5=2+2+1=2+1+1+1=1+1+1+1+1.

Входные данные

Программа получает на вход натуральное число n,
не превышающее 100.

Выходные данные

Выведите ответ на задачу.

Решение

Решить
данную задачу можно следующим образом:

s = int(input())

cnt = 0

for a
in range(11):

    for b
in range(21):

       
for c in range(51):

           
for d in range(101):

               
if a*10+b*5+c*2+d == s:

                   
cnt+=1

 print(cnt)

Выдача сдачи — 2

 

Имеется неограниченное количество монет в 1, 2, 5, 10 рублей.
Определите, сколькими способами можно выдать сдачу в nn рублей. Например, 55 рублей можно выдать четырьмя способами: 5=2+2+1=2+1+1+1=1+1+1+1+1.

Входные данные

Программа получает на вход натуральное число n,
не превышающее 10⁶.

Выходные данные

Выведите ответ на задачу.

Примечание

Правильное решение задачи можно написать, используя всего
один цикл while.

Решение

Ещё один классический способ:

n > 0 && (n & (n - 1)) == 0

---

Там по ссылке ещё много всяких битовых трюков.

---

Как это трюк работает? А вот как. Запишем число n в двоичной системе, и рассмотрим самую правую единицу в двоичном представлении числа n. У числа n - 1 будет на месте этой единицы ноль, а справа от него единицы:

n      : xxxxxx1000
1      : 0000000001
n - 1  : xxxxxx0111

а остальные двоичные цифры (обозначенные как x) не поменяются. Поэтому после операции & получится вот что:

n&(n-1): xxxxxx0000

Это число будет равно нулю тогда и только когда, когда все xxxxxx равны нулю. Единственный случай, где наше соображение не проходит — число 0: там нету «самой правой» единицы вовсе, так что это случай приходится рассматривать отдельно.

---

Интересно, что gcc и clang выдают на этот код и код из ответа @aepot строго одинаковый ассемблерный код: https://godbolt.org/z/xWx1qT

Тебе же в прошлом вопросе разжевали всё, зачем снова плодить глупые вопросы? Но если ты прошлый вопрос спрашивал, чтобы таким образом проверять на степень двойки, то лучше сразу уходи их профессии. Изучи хотя бы основы построения алгоритмов.

Нормальная и быстрая проверка на степень двойки делается через бинарные операции:

def check2rec(num):
    if num == 1:
        return True
    if num & 1:
        return False
    return check2rec(num >> 1)

Плюс, эту функцию можно ещё пооптимизировать.

Ну и бенчмарки, чтобы доказать ущербность логарифмического метода:

def check2rec(num):
    if num == 1:
        return True
    if num & 1:
        return False
    return check2rec(num >> 1)

def check2log(num):
    r = log(num, 2)
    return int(r) == r

numbers = list()
print('Generating numbers...')
for _ in range(1000):
    numbers.append(randint(10000, 1000000))
print('Done!')

start = datetime.datetime.now()
for _ in range(10000):
    for n in numbers:
        check2rec(n)
print('Rec: ', datetime.datetime.now() - start)

start = datetime.datetime.now()
for _ in range(10000):
    for n in numbers:
        check2log(n)
print('Log: ', datetime.datetime.now() - start)

Результаты:

Rec:  0:00:07.408942
Log:  0:00:12.101660

Разница почти в 2 раза.

P.S. С такими «знаниями» тебя в более-менее приличное место не возьмут никогда. Изучи сперва программирование (т.е. построение алгоритмов), а не язык. Почитай Вирта, Кормена, или SICP.