Что значит точная степень двойки
Является ли число степенью двойки?
Прошу помочь найти ошибку. Смотрю на код, рассуждаю, вроде всё должно работать. Варианты с функциями и for не рассматриваются. Хочу разобраться именно в этом примере.
Проверить, является ли число n точной степенью двойки
2) Ввести число n с клавиатуры. Если число n является точной степенью двойки, вывести “YES”, в.
Проверить, является ли заданное натуральное число степенью двойки
Здравствуйте, форумчане. Есть следующее задание: Дано натуральное число N. Выведите слово.
Написать функцию power_of_two, которая определяет является ли заданное число степенью двойки
# Написать функцию power_of_two, которая определяет является ли заданное число степенью двойки. #.
Проверить является ли число степенью тройки
def is_power_three(n): print(n) if n == 1: return ‘Є степенем трійки’ if n.
Так а что вывести-то, если входное число является степенью 2-ки. Само число или степень?
Добавлено через 43 секунды
Вот если надо степень вывести
Решение
FFPowerMan, вывести надо степень
Добавлено через 3 минуты
Буду разбираться с двумя последними кодами, спасибо большое
Решение
Решение
Проверить, является ли число a степенью числа b
Решите задачу одним циклом while, допускается применение условных операторов. Задано два числа a.
Является число степенью двойки?
Доброго времени суток, форумчане!) Есть массив чисел ($user), который нужно проверить и найти в.
Является ли число степенью двойки
Помогите с ошибкой, не могу понять что не то. Нужно вычислить являеться ли число степенью двойки.
Рекурсия. Занимательные задачки
В этой статье речь пойдет о задачах на рекурсию и о том как их решать. 
Кратко о рекурсии
Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Один из вариантов увидеть рекурсию – это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив. Таким образом, камера будет записывать изображение экрана компьютера, и выводить его же на этот экран, получится что-то вроде замкнутого цикла. В итоге мы будем наблюдать нечто похожее на тоннель.
В программировании рекурсия тесно связана с функциями, точнее именно благодаря функциям в программировании существует такое понятие как рекурсия или рекурсивная функция. Простыми словами, рекурсия – определение части функции (метода) через саму себя, то есть это функция, которая вызывает саму себя, непосредственно (в своём теле) или косвенно (через другую функцию).
Задачи
При изучении рекурсии наиболее эффективным для понимания рекурсии является решение задач.
Любой алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационном виде и наоборот. Останется вопрос, надо ли это, и насколько это будет это эффективно.
Для обоснования можно привести такие доводы.
Для начала можно вспомнить определение рекурсии и итерации. Рекурсия — это такой способ организации обработки данных, при котором программа вызывает сама себя непосредственно, либо с помощью других программ. Итерация — это способ организации обработки данных, при котором определенные действия повторяются многократно, не приводя при этом к рекурсивным вызовам программ.
После чего можно сделать вывод, что они взаимно заменимы, но не всегда с одинаковыми затратами по ресурсам и скорости. Для обоснования можно привести такой пример: имеется функция, в которой для организации некого алгоритма имеется цикл, выполняющий последовательность действий в зависимости от текущего значения счетчика (может от него и не зависеть). Раз имеется цикл, значит, в теле повторяется последовательность действий — итерации цикла. Можно вынести операции в отдельную подпрограмму и передавать ей значение счетчика, если таковое есть. По завершению выполнения подпрограммы мы проверяем условия выполнения цикла, и если оно верно, переходим к новому вызову подпрограммы, если ложно — завершаем выполнение. Т.к. все содержание цикла мы поместили в подпрограмму, значит, условие на выполнение цикла помещено также в подпрограмму, и получить его можно через возвращающее значение функции, параметры передающееся по ссылке или указателю в подпрограмму, а также глобальные переменные. Далее легко показать, что вызов данной подпрограммы из цикла легко переделать на вызов, или не вызов (возврата значения или просто завершения работы) подпрограммы из нее самой, руководствуясь какими-либо условиями (теми, что раньше были в условии цикла). Теперь, если посмотреть на нашу абстрактную программу, она примерно выглядит как передача значений подпрограмме и их использование, которые изменит подпрограмма по завершению, т.е. мы заменили итеративный цикл на рекурсивный вызов подпрограммы для решения данного алгоритма.
Задача по приведению рекурсии к итеративному подходу симметрична.
Подводя итог, можно выразить такие мысли: для каждого подхода существует свой класс задач, который определяется по конкретным требованиям к конкретной задаче.
Более подробно с этим можно познакомиться тут
Так же как и у перебора (цикла) у рекурсии должно быть условие остановки — Базовый случай (иначе также как и цикл рекурсия будет работать вечно — infinite). Это условие и является тем случаем к которому рекурсия идет (шаг рекурсии). При каждом шаге вызывается рекурсивная функция до тех пор пока при следующем вызове не сработает базовое условие и произойдет остановка рекурсии(а точнее возврат к последнему вызову функции). Всё решение сводится к решению базового случая. В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение.
Тут Базовым условием является условие когда n=1. Так как мы знаем что 1!=1 и для вычисления 1! нам ни чего не нужно. Чтобы вычислить 2! мы можем использовать 1!, т.е. 2!=1!*2. Чтобы вычислить 3! нам нужно 2!*3… Чтобы вычислить n! нам нужно (n-1)!*n. Это и является шагом рекурсии. Иными словами, чтобы получить значение факториала от числа n, достаточно умножить на n значение факториала от предыдущего числа.
В сети при обьяснении рекурсии также даются задачи нахождения чисел Фибоначчи и Ханойская башня
Рассмотрим же теперь задачи с различным уровнем сложности.
Попробуйте их решить самостоятельно используя метод описанный выше. При решении попробуйте думать рекурсивно. Какой базовый случай в задаче? Какой Шаг рекурсии или рекурсивное условие?
Поехали! Решения задач предоставлены на языке Java.
A: От 1 до n
Дано натуральное число n. Выведите все числа от 1 до n.
Является ли число степенью двойки
Эта статья посвящена одной из наипопулярнейших задач в области программирования. Сложно представить себе программиста, который хотя бы раз в своей карьере не сталкивался с ней.
Существует целый ряд способов её решения. В этой статье будут рассмотрены два, наиболее грамотные из них.
Данные методы считаются таковыми не только в силу своей вычислительной эффективности, но и прежде всего потому, что имеют объективное математическое обоснование.
1.Использование битовых операций
Или в варианте C++ и ему подобных языков
Данное число n является степенью числа 2 или числом 0. Отдельное внимание заслуживает число 1, которое является числом 2 в степени 0.
Таким образом, чтобы проверка была корректной необходимо исключить числа 0 и 1. Например, так:
Или в варианте для C++:
2.Использование логарифмов
Этот способ уже был подробно описан в статье «Является ли число степенью другого числа». В данном способе задача проверки, является ли число степенью двойки, рассматривается как частный случай задачи рассмотренной там.
Для выполнения проверки необходимо вычислить логарифм числа по основанию 2 или частное логарифмов проверяемого числа и числа 2 по общему основанию и проверить является ли результат целым числом.
Если используемый язык программирования или библиотека имеют готовую функцию для вычисления логарифма по основанию 2, решение упрощается до предела.
Степени двойки
Этот вспомогательный материал, который может быть полезен для подготовки к ГИА по информатике, в частности задач 15 ГИА, задач 1 ГИА, B10 ЕГЭ по информатике
Степени двойки таблица
| 2 0 | 1 |
| 2 1 | 2 |
| 2 2 | 4 |
| 2 3 | 8 |
| 2 4 | 16 |
| 2 5 | 32 |
| 2 6 | 64 |
| 2 7 | 128 |
| 2 8 | 256 |
| 2 9 | 512 |
| 2 10 | 1024 |
| 2 11 | 2048 |
| 2 12 | 4096 |
| 2 13 | 8192 |
| 2 14 | 16384 |
| 2 15 | 32768 |
| 2 16 | 65536 |
| 2 17 | 131072 |
| 2 18 | 262144 |
| 2 19 | 524288 |
| 2 20 | 1048576 |
Автор: Александр Чернышов
Оцените статью, это очень поможет развитию сайта.
Всего лишь степени двойки
Несомненно, многие читатели встречали ее в классической истории об изобретателе шахмат, который попросил у правителя в награду за первую клетку шахматной доски одно пшеничное зерно, за вторую — два, за третью — четыре, и так далее, всё время удваивая число зерен. Понятно, что суммарное их количество равно
Но так как эта сумма неимоверно велика и во много раз превосходит годовой урожай зерновых по всему миру, вышло, что мудрец ободрал правителя как липку. 1
Однако зададимся сейчас другим вопросом: как с наименьшими затратами труда подсчитать величину S? Обладатели калькулятора (или, паче того, компьютера) вполне могут за обозримое время выполнить перемножения, а затем сложить полученные 64 числа, получив ответ: 18 446 744 073 709 551 615. А поскольку объем вычислений немалый, то и вероятность ошибки весьма велика.
Кто похитрей, могут углядеть в этой последовательности геометрическую прогрессию. Не знакомые же с этим понятием (или те, кто попросту забыл стандартную формулу суммы геометрической прогрессии) могут использовать следующие рассуждения. Давайте-ка умножим обе части равенства (1) на 2. Так как при удвоении степени двойки ее показатель увеличивается на 1, то получим
Теперь из (2) вычтем (1). В левой части, понятное дело, получится 2S – S = S. В правой же части произойдет массовое взаимное уничтожение почти всех степеней двойки — от 2 1 до 2 63 включительно, и останется лишь 2 64 – 2 0 = 2 64 – 1. Итак:
Что ж, выражение заметно упростилось, и теперь, имея калькулятор, позволяющий возводить в степень, можно найти значение этой величины без малейших проблем.
А если и калькулятора нет — как быть? Перемножать в столбик 64 двойки? Еще чего не хватало! Опытный инженер или математик-прикладник, для которого главный фактор — время, сумел бы быстро оценить ответ, т.е. найти его приближенно с приемлемой точностью. Как правило, в быту (да и в большинстве естественных наук) вполне допустима погрешность в 2–3%, а если она не превосходит 1% — то это просто великолепно! Оказывается, подсчитать наши зерна с такой погрешностью можно вообще без калькулятора, и всего за несколько минут. Как? Сейчас увидите.
Поэтому 1,024 6 = (1 + 0,24) 6 ≈ 1 + 0,24·6 = 1,144. Посему надо найденное нами число 16·10 18 умножить на число 1,144, в результате чего получится 18 304 000 000 000 000 000, а это отличается от правильного ответа менее чем на 1%. Чего мы и добивались!
Другая интересная особенность рассматриваемой последовательности заключается в том, что любое натуральное число можно построить из различных степеней двойки, причем единственным способом. Например, для номера текущего года имеем
Фактически мы только что обосновали возможность записи чисел в двоичной системе счисления. Как известно, в ней используются лишь две цифры — ноль и единица, и каждое натуральное число записывается в двоичной системе единственным способом (например, упомянутое выше 2012 — как 11 111 011 100). Если пронумеровать разряды (двоичные цифры) справа налево, начиная с нуля, то номера тех разрядов, в которых стоят единицы, как раз и будут показателями степеней двоек, входящих в представление. 3
Как ни удивительно, но любое целое число можно (и притом единственным способом) представить в виде суммы различных слагаемых нашей «положительно-отрицательной» последовательности. 4 И доказать это не очень-то сложно (например, индукцией по показателям степеней двоек). Главная идея доказательства — наличие сколь угодно больших по абсолютной величине как положительных, так и отрицательных слагаемых. Попробуйте выполнить доказательство сами.
Итак, на последние цифры степеней двойки наложены довольно жесткие ограничения. А как насчет первых цифр? Здесь ситуация практически противоположная. Оказывается, для любого набора цифр (первая из которых — не ноль) найдется степень двойки, начинающаяся с этого набора цифр. И таких степеней двойки бесконечно много! Например, существует бесконечное количество степеней двойки, начинающихся с цифр 2012 или, скажем, 3 333 333 333 333 333 333 333.
А если рассмотреть только одну самую первую цифру различных степеней двойки — какие значения она может принимать? Нетрудно убедиться, что любые — от 1 до 9 включительно (нуля среди них, естественно, нет). Но какие из них встречаются чаще, а какие реже? Как-то сразу не видно причин, по которым одна цифра должна встречаться чаще другой. Однако более глубокие размышления показывают, что как раз равной встречаемости цифр ожидать не приходится. Действительно, если первая цифра какой-либо степени двойки есть 5, 6, 7, 8 или 9, то первая цифра следующей за ней степени двойки будет обязательно единицей! Поэтому должен иметь место «перекос», по крайней мере, в сторону единицы. Следовательно, вряд ли и остальные цифры будут «равнопредставленными».
Практика (а именно — прямой компьютерный расчет для первых нескольких десятков тысяч степеней двойки) подтверждает наши подозрения. Вот какова относительная доля первых цифр степеней двойки с округлением до 4 знаков после запятой:
1 — 0,3010
2 — 0,1761
3 — 0,1249
4 — 0,0969
5 — 0,0792
6 — 0,0669
7 — 0,0580
8 — 0,0512
9 — 0,0458
Степени двойки также являются своеобразным «генератором» для производства широко известных совершенных чисел, которые равны сумме всех своих делителей, за исключением себя самого. Например, у числа 6 четыре делителя: 1, 2, 3 и 6. Отбросим тот, который равен самому числу 6. Осталось три делителя, сумма которых как раз равна 1 + 2 + 3 = 6. Поэтому 6 — совершенное число.
Тесную связь имеют степени двойки с так называемыми числами Каталана, последовательность которых имеет вид 1, 1, 2, 5, 14, 42, 132, 429. Они часто возникают при решении различных комбинаторных задач. Например, сколькими способами можно разбить выпуклый n-угольник на треугольники непересекающимися диагоналями? Всё тот же Эйлер выяснил, что это значение равно (n – 1)-му числу Каталана (обозначим его Kn–1), и он же выяснил, что Kn = Kn–1·(4n – 6)/n. Последовательность чисел Каталана имеет множество любопытных свойств, и одно из них (как раз связанное с темой этой статьи) заключается в том, что порядковые номера всех нечетных чисел Каталана являются степенями двойки!
Степени двойки нередко встречаются в различных задачах, причем не только в условиях, но и в ответах. Возьмем, например, популярную когда-то (да и поныне не забытую) Ханойскую башню. Так называлась игра-головоломка, придуманная в XIX веке французским математиком Э. Люка. Она содержит три стержня, на один из которых надето n дисков с отверстием в середине каждого. Диаметры всех дисков различны, и они расположены в порядке убывания снизу вверх, т. е. самый большой диск — внизу (см. рисунок). Получилась как бы башня из дисков.
Требуется перенести эту башню на другой стержень, соблюдая такие правила: перекладывать диски строго по одному (снимая верхний диск с любого стержня) и всегда класть только меньший диск на больший, но не наоборот. Спрашивается: какое наименьшее число ходов для этого потребуется? (Ходом мы называем снятие диска с одного стержня и надевание его на другой.) Ответ: оно равно 2 n – 1, что легко доказывается по индукции.
Пусть для n дисков потребное наименьшее число ходов равно Xn. Найдем Xn+1. В процессе работы рано или поздно придется снимать самый большой диск со стержня, на который первоначально были надеты все диски. Так как этот диск можно надевать только на пустой стержень (иначе он «придавит» меньший диск, что запрещено), то все верхние n дисков придется предварительно перенести на третий стержень. Для этого потребуется не меньше Xn ходов. Далее переносим наибольший диск на пустой стержень — вот еще один ход. Наконец, чтобы сверху его «притиснуть» меньшими n дисками, опять потребуется не меньше Xn ходов. Итак, Xn+1 ≥ Xn + 1 + Xn = 2Xn + 1. С другой стороны, описанные выше действия показывают, как можно справиться с задачей именно 2Xn + 1 ходами. Поэтому окончательно Xn+1 =2Xn + 1. Получено рекуррентное соотношение, но для того чтобы его привести к «нормальному» виду, надо еще найти X1. Ну, это проще простого: X1 = 1 (меньше просто не бывает!). Не составляет труда, основываясь на этих данных, выяснить, что Xn = 2 n – 1.
Вот еще одна интересная задача:
Найдите все натуральные числа, которые нельзя представить в виде суммы нескольких (не менее двух) последовательных натуральных чисел.
Давайте проверим сначала наименьшие числа. Ясно, что число 1 в указанном виде непредставимо. Зато все нечетные, которые больше 1, представить, конечно, можно. В самом деле, любое нечетное число, большее 1, можно записать как 2k + 1 (k — натуральное), что есть сумма двух последовательных натуральных чисел: 2k + 1 = k + (k + 1).
А как обстоят дела с четными числами? Легко убедиться, что числа 2 и 4 нельзя представить в требуемом виде. Может, и для всех четных чисел так? Увы, следующее же четное число опровергает наше предположение: 6 = 1 + 2 + 3. Зато число 8 опять не поддается. Правда, следующие числа вновь уступают натиску: 10 = 1 + 2 + 3 + 4, 12 = 3 + 4 + 5, 14 = 2 + 3 + 4 + 5, а вот 16 — вновь непредставимо.
Что ж, накопленная информация позволяет сделать предварительные выводы. Обратите внимание: не удалось представить в указанном виде только степени двойки. Верно ли это для остальных чисел? Оказывается, да! В самом деле, рассмотрим сумму всех натуральных чисел от m до n включительно. Так как всего их, по условию, не меньше двух, то n > m. Как известно, сумма последовательных членов арифметической прогрессии (а ведь именно с ней мы имеем дело!) равна произведению полусуммы первого и последнего членов на их количество. Полусумма равна (n + m)/2, а количество чисел равно n – m + 1. Поэтому сумма равна (n + m)(n – m + 1)/2. Заметим, что в числителе находятся два сомножителя, каждый из которых строго больше 1, и при этом четность их — различна. Выходит, что сумма всех натуральных чисел от m до n включительно делится на нечетное число, большее 1, и потому не может быть степенью двойки. Так что теперь понятно, почему не удалось представить степени двойки в нужном виде.
Вот и всё. Итак, ответ: непредставимые числа — это степени двойки, и только они.
А вот еще одна задача (впервые ее предложил В. Произволов, но в несколько иной формулировке):
Садовый участок окружен сплошным забором из N досок. Согласно приказу тети Полли Том Сойер белит забор, но по собственной системе: продвигаясь всё время по часовой стрелке, сначала белит произвольную доску, затем пропускает одну доску и белит следующую, затем пропускает две доски и белит следующую, затем пропускает три доски и белит следующую, и так далее, каждый раз пропуская на одну доску больше (при этом некоторые доски могут быть побелены несколько раз — Тома это не смущает).
Том считает, что при такой схеме рано или поздно все доски будут побелены, а тетя Полли уверена, что хотя бы одна доска останется непобеленной, сколько бы Том ни работал. При каких N прав Том, а при каких — тетя Полли?
Описанная система побелки представляется довольно хаотичной, поэтому первоначально может показаться, что для любого (или почти любого) N каждой доске когда-нибудь достанется своя доля известки, т. е., в основном, прав Том. Но первое впечатление обманчиво, потому что на самом деле Том прав только для значений N, являющихся степенями двойки. Для остальных N найдется доска, которая так и останется навеки непобеленной. Доказательство этого факта довольно громоздко (хотя, в принципе, несложно). Предлагаем читателю выполнить его самому.
Вот каковы они — степени двойки. С виду — проще простого, а как копнешь. И затронули мы здесь далеко не все удивительные и загадочные свойства этой последовательности, а лишь те, что бросились в глаза. Ну, а читателю предоставляется право самостоятельно продолжить исследования в этой области. Несомненно, они окажутся плодотворными.