Даны два числа вывести все степени числа

Решение задач на С++

понедельник, 14 марта 2011 г.

Операторы цикла

Цикл While. Блок 1. Задачи на цикл While.

Задача A. Список квадратов
Выведите все точные квадраты натуральных чисел, не превосходящие данного числа N.

1. int n;
2. cin>>n;
3. int value = 1;
4. int curSqr = value * value ;
5. while (curSqr ‘ ‘ ;
6. value ++;
7. curSqr = value * value ;
8. >

* This source code was highlighted with Source Code Highlighter .

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

1. int n;
2. cin >> n;
3. int i = 2, min_den = 1;
4. int sqrt_n = sqrt(( double )n);
5. while (i if (n % i == 0)
6. <
7. min_den = i;
8. break ;
9. >
10. i++;
11. >
12. if (min_den == 1)
13. cout else
14. cout * This source code was highlighted with Source Code Highlighter .

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

Той же самой цели можно добиться, заменив явное умножение на 2 побитовым сдвигом.
Вариант 2.

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

1. int n;
2. cin>>n;
3. int bitAmount = 0;
4. while (n) <
5. bitAmount += n % 2;
6. n /= 2;
7. >
8. if (bitAmount == 1)
9. cout «YES» ;
10. else
11. cout «NO» ;

* This source code was highlighted with Source Code Highlighter .

Задача E. Двоичный логарифм
По данному натуральному числу N выведите такое наименьшее целое число k, что 2 k ≥N.
Операцией возведения в степень пользоваться нельзя!

1. int n;
2. cin >> n;
3. int pow2 = 1, k = 0;
4. while (pow2 * This source code was highlighted with Source Code Highlighter .

Задача F. Утренняя пробежка
В первый день спортсмен пробежал x километров, а затем он каждый день увеличивал пробег на 10% от предыдущего значения. По данному числу y определите номер дня, на который пробег спортсмена составит не менее y километров.
Программа получает на вход действительные числа x и y и должна вывести одно натуральное число.

Задача G. Банковские проценты
Вклад в банке составляет x рублей. Ежегодно он увеличивается на p процентов, после чего дробная часть копеек отбрасывается. Каждый год сумма вклада становится больше. Определите, через сколько лет вклад составит не менее y рублей.
Программа получает на вход три натуральных числа: x, p, y и должна вывести одно целое число.

1. int n, i = 2, f1 = 0, f2 = 1, cur;
2. cin >> n;
3. while (i if (n else
4. cout * This source code was highlighted with Source Code Highlighter .

Задача I. Номер числа Фибоначчи
Дано натуральное число A. Определите, каким по счету числом Фибоначчи оно является, то есть выведите такое число n, что φ_n=A. Если А не является числом Фибоначчи, выведите число -1.

1. int a, i = 1, f1 = 0, f2 = 1, cur = 1;
2. cin >> a;
3. while (cur if (cur == a)
4. cout else
5. cout * This source code was highlighted with Source Code Highlighter .

Задача J. Исполнитель Раздвоитель
Исполнитель “Раздвоитель” преобразует натуральные числа. У него есть две команды: “Вычесть 1” и “Разделить на 2”, первая команда уменьшает число на 1, вторая команда уменьшает число в два раза, если оно чётное, иначе происходит ошибка.
Дано два натуральных числа A и B (A>B). Напишите алгоритм для Раздвоителя, который преобразует число A в число B и при этом содержит минимальное число команд. Команды алгоритма нужно выводить по одной в строке, первая команда обозначается, как -1, вторая команда как :2.

Задача K. Исполнитель Водолей
У исполнителя “Водолей” есть два сосуда, первый объемом A литров, второй объемом B литров, а также кран с водой. Водолей может выполнять следующие операции:
Наполнить сосуд A (обозначается >A).
Наполнить сосуд B (обозначается >B).
Вылить воду из сосуда A (обозначается A>).
Вылить воду из сосуда B (обозначается B>).
Перелить воду из сосуда A в сосуд B (обозначается как A>B).
Перелить воду из сосуда B в сосуд A (обозначается как B>A).
Команда переливания из одного сосуда в другой приводят к тому, что либо первый сосуд полностью опустошается, либо второй сосуд полностью наполняется.
Программа получает на вход три натуральных числа A, B, N, не превосходящих 10 4 Вам необходимо вывести алгоритм действий Водолея, который позволяет получить в точности N литров в одном из сосудов, если же такого алгоритма не существует, то программа должна вывести текст Impossible. Количество операций в алгоритме не должно превышать 10 5 . Гарантируется, что если задача имеет решение, то есть решение, которое содержит не более, чем 10 5 операций.

1. const int LIMIT = 1e5 + 10;
2. int a, b, n;
3. cin >> a >> b >> n;
4. char min = ‘A’ , max = ‘B’ ;
5. bool real = false ;
6. if (b int bV = 0, aV = 0;
7. int k = 0;
8. do
9. <
10. k++; /*printf(«>%c\n»,min);*/
11. k++; /*printf(«%c>%c\n», min, max);*/
12. if (b — bV >= a)
13. bV += a;
14. else
15. <
16. bV = a — (b — bV);
17. k++; /*printf(«%c>\n»,max);*/
18. k++; /*printf(«%c>%c\n», min, max);*/
19. >
20. if (n == bV)
21. <
22. real = true ;
23. break ;
24. >
25. >
26. while (k if (real)
27. <
28. bV = 0;
29. do
30. <
31. printf( «>%c\n» ,min);
32. printf( «%c>%c\n» , min, max);
33. if (b — bV >= a)
34. bV += a;
35. else
36. <
37. bV = a — (b — bV);
38. printf( «%c>\n» ,max);
39. printf( «%c>%c\n» , min, max);
40. >
41. if (n == bV)
42. break ;
43. >
44. while ( true );
45. >
46. else
47. cout «Impossible» ;

* This source code was highlighted with Source Code Highlighter .

Источник

Цикл while

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

i = 0
while i 5 :
print (i)
i += 1

Цикл while и цикл for имеют схожую структуру, НО есть одно важное различие — цикл while может быть бесконечным.

i = 0
while True :
print (i)
i += 1

# Вывод:
>>> 0
>>> 1
>>> 2
>>> 3
>>> 4
# Это может продолжаться долго.

Код выше будет бесконечно печатать возрастаютщую последовательность чисел.

Цикл while можно сравнить с цикличным условным оператором.

text = ‘Hello world’
i = 0
while i len (text):
print (text[i])
i += 1

Код, приведенный выше, печатает строку посимвольно. Приведу пример аналогичного цикла for:

text = ‘Hello world’
for i in text:
print (i)

Более того, я приведу даже два цикла for!

text = ‘Hello world’
for i in range ( len (text)):
print (text[i])

Напомню, что отличие между двумя, приведенными выше примерами, в следующем: первый цикл проходит по элементам последовательности (в нашем случае строки), а второй — по ее индексам. Здесь также используется функция len(), которая позволяет узнать длину последовательности.

Вернемся к циклу while. Цикл while, как и цикл for, можно остановить с помощью специальной управлющей конструкции break.

j = 0
while True :
if j == 3 :
print ( ‘Выход из цикла’ )
break
print (j)
j += 1

Конструкция break прерывает цикл. Она очень похожа на обычное условие после ключевого слова while.

Так же есть еще одна управляющая конструкция — continue. С ее помощью мы можем не выпонять текущую итерацию (повторение) цикла и перейти сразу к следующему.

j = 0
while j 5 :
j += 1
if j == 3 :
print ( ‘Пропускаем j == 3 ‘ )
continue
print (j)

Как и для цикла for, для цикла while мы можем записать конструкцию else.

from random import randint
j = 0
element = randint ( 0 , 15 )
while j 10 :
j += 1
if j == element:
print ( ‘Нашли element, он равен’ , element)
break
else :
print ( ‘Неудачная попытка’ )

Примеры решения задач

Возведение числа в степень с помощью цикла while

n = int ( input ()) # число
k = int ( input ()) # степень
i = 1 # текущая степень
result = 1
while i k:
result *= n
i += 1
print (result)

Сумма последовательности с помощью цикла while

n = int ( input ())
result = 0
i = 0
while i n:
result += i
i += 1
print (result)

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

i = 0
while True :
n = input ()
if n == ‘end’ :
print ( ‘Ввод закончен’ )
print ( ‘Было введено’ , i, ‘чисел’ )
break
n = int (n)
i += 1

Сумма введенных чисел

i = 0
summa = 0
while True :
n = input ()
if n == ‘end’ :
print ( ‘Ввод закончен’ )
print ( ‘Было введено’ , i, ‘чисел’ )
print ( ‘Их сумма равна’ , summa)
break
n = int (n)
summa += n
i += 1

Решение задач

1. Дано положительное число N. Вывести все числа от 0 до N с помощью цикла while.

2. Дано положительное число N. Вывести все числа от N до 0 с помощью цикла while. Пример:

3. Даны два положительных числа K и N (K 4. Даны положительные числа A и B (A > B). На отрезке длины A размещено максимально возможное количество отрезков длины B (без наложений). Не используя операции умножения и деления, найти длину незанятой части отрезка A (взятие остатка A % B)

5. Даны положительные числа A и B (A > B). На отрезке длины A размещено максимально возможное количество отрезков длины B (без наложений). Не используя операции умножения и деления, найти количество отрезков B, размещенных на отрезке A (деление нацело A // B)

6. Дано положительное число N. Найти сумму всех четных чисел от 0 до N с помощью цикла while.

7. Даны два положительных числа K и N (K нечетных чисел от K до N с помощью цикла while.

8. Дано положительное число N. Найти факториал числа N. Факториалом числа называется произведение всех чисел от 1 до N. Например, факториал числа 5 равен 5! = 1*2*3*4*5 = 120 , 2! = 1*2 = 2 , 9! = 1*2*3*4*5*6*7*8*9 = 362880

9. Дано целое число N (> 0). Если оно является степенью числа 3, то вывести YES, если не является — вывести NO.

10. Дано целое число N (> 0). Найти двойной факториал N: N!! = N * (N-2) * (N-4)* . . Для решения этой задачи посмотрите на задачу 2

Сложные задачи

1. Дано целое число N (> 1). Найти наименьшее целое число K, при котором выполняется неравенство 3^K > N, где 3^K — это 3 в степени K или число 3, умноженное само на себя K раз. Например, 3^5 = 3*3*3*3*3 . Ответом в задаче будет первая степень числа 3, которая больше, чем заданное число N. Например, если N=41, распишем степени числа три: 3^1 = 3; 3^2 = 3*3 = 9; 3^3 = 3*3*3 = 27; 3^4 = 3*3*3*3 = 27 * 3 = 81; . Таким образом, первая степень, в которую возвести число 3, превышающая число N — это 4.
В этой задаче нужно выполнять цикл while, пока остаток от деления на число три равен 0

2. Дано целое число N (> 0). Используя операции деления нацело и взятия остатка от деления, вывести все его цифры, начиная с самой правой (разряда единиц).
Перед решением этой задачи вспомните, как найти сумму цифр трехначного числа.

3. Даны целые положительные числа A и B. Найти их наибольший общий делитель (НОД), используя алгоритм Евклида: НОД(A, B) = НОД(B, A mod B), если B = 0; НОД(A, 0) = A.

4. Спортсмен-лыжник начал тренировки, пробежав в первый день 10 км. Каждый следующий день он увеличивал длину пробега на P процентов от пробега предыдущего дня (P — вещественное, 0 5. Дано целое число N (> 1). Последовательность чисел Фибоначчи FK определяется следующим образом: F(1) = 1, F(2) = 1, F(K) = F(K-2) + F(K-1), K = 3, 4, . . Проверить, является ли число N числом Фибоначчи. Если является, то вывести TRUE, если нет — вывести FALSE.

6. Даны положительные числа A, B, C. На прямоугольнике размера A x B размещено максимально возможное количество квадратов со стороной C (без наложений). Найти количество квадратов, размещенных на прямоугольнике. Операции умножения и деления не использовать.

7. Дано целое число N (> 1), являющееся числом Фибоначчи: N = F(K). Найти целое число K — порядковый номер числа Фибоначчи N.

Источник

Рекурсия. Занимательные задачки

В этой статье речь пойдет о задачах на рекурсию и о том как их решать.

Кратко о рекурсии

Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Один из вариантов увидеть рекурсию – это навести 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.

Источник