Комбинаторика, как решить: номера всех кабинетов сделать счастливыми(см.)?
Задача на комбинаторику С++
В новом здании налоговой инспекции было решено номера всех кабинетов сделать счастливыми.
Счастливым называется номер, состоящий только из цифр 7 и 8. Найдите максимальное количество кабинетов в новом здании налоговой инспекции, если на табличку с номером кабинета помещается не более чем n-значное число.
Входные данные
Единственная строка входных данных содержит одно целое число n (1 ≤ n ≤ 55) — максимальная длина числа, которое помещается на табличку.
Выходные данные
Выведите одно целое число — максимальное количество кабинетов, которые можно занумеровать различными счастливыми номерами длины не более n.
Ответы (2)
Номеров, состоящих из одной цифры - два (7 или 8). Количество номеров из не более, чем n цифр 7 или 8, равно сумме геометрической прогрессии с первым членом 2 и знаменателем 2:
2^(n+1)-2 = 2(2^n-1).
Таким образом, программа по введённому числу n должна выдавать число 2(2^n-1).
вам код на С++ написать?
ответ - (2^1 + 2^2 + 2^3 + ... +2^n) - сумма степеней двойки.
для числа строго из n символов будет 2^n комбинаций (в каждом из n разрядов может быть два варианта - 7 и 8)
но номера кабинетов могут быть и короче. то есть, надо прибавить ещё все варианты для (n-1).
псевдокод примерно такой (не проверяла)
res=0;
for(int i = 1; i<=n; i++){
res += 1<<i; // прибавляем 2 в степени i
}
ВКонтакте