Форум программистов, компьютерный форум, киберфорум
Наши страницы

Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Синхронизация потоков в c++ http://www.cyberforum.ru/cpp-beginners/thread945396.html
Совершенно не понятно что не так и как правильно. Задача: Отсортировать массив целых чисел. Программу разбить на два синхронизированных потока. Объект синхронизации на свое усмотрение. Я выбрал...
C++ Написать пару функций Max, возвращающих то из чисел, которое было передано большее число раз Задание: Реализуйте пару функций Max, принимающих два целочисленнных параметра и два числа с плавающей точкой соответственно и возвращающих то из чисел, которое было передано этой функции большее... http://www.cyberforum.ru/cpp-beginners/thread945392.html
Оператор для xor шифрования C++
Разматриваю пример шифрования, возник детский вопрос ^ что делает этот оператор?
C++ Класс Time через time(0)
Всем привет. На форуме искал ничего похожего не нашол. Не могу до конца разобраться. В класе 1 член, который держит секунды, которые берутся в конструкторе функцией time(0). Нада вывести...
C++ Почему я не могу создать статический элемент класса fstream? http://www.cyberforum.ru/cpp-beginners/thread945352.html
Ошибка: Compiling... static_fstream.cpp Linking... static_fstream.obj : error LNK2001: unresolved external symbol "private: static class std::basic_fstream<char,struct std::char_traits<char> >...
C++ Нарисовать карту, отслеживать координаты остановок Задача заключается в том что надо нарисовать карту в которой есть дороги, остановки, маршрутные пути... При в воде 2-х остановок программа должна показать все возможные номера маршруток на которых... подробнее

Показать сообщение отдельно
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6523 / 3162 / 311
Регистрация: 04.12.2011
Сообщений: 8,764
Записей в блоге: 5
30.08.2013, 13:42
Цитата Сообщение от Somebody Посмотреть сообщение
IGPIGP, если в этом "каркасе" заменить несколько нулей на единицы, то уже появляется возможность заменить какие-то единицы на нули.
1010 -> 1101
Да. Сыровато получилось.
Особенно самая последняя формула.
Тем не менее, именно каркас для четных чисел и есть пока главная ценность представленной идеи. Плохо, что к чистой рекурсии, он приводит только для чисел c длиной вида 2^n
Смотрите, только в четном числе каркас однозначен. Например в записи:
10101010
нельзя сдвинуть ни одну единицу. Но тогда для числа:
11111101 a=1, b=7 на этом каркасе (10101010)
получаем вопрос: сколько можно построить чисел из 7-4=3 единиц (избытка над каркасом) на 4-х нулях (свободных нулях каркаса)
И для чисел длина которых 2^n , можно делить пока есть свободные единицы.
Для нечётных всё сложнее. Пока удалось додуматься, что для записи длиной n = 2k+1 можно построить k+1 каркасов. То есть не один:
для 3 -> 2
101
110
для 5 -> 3
10101
10110
11010
для 7 -> 4
...
Далее еще видно, что каждый каркас нечётного, можно получить из каркаса предыдущего чётного, приписав в конце 1 или записав 1 рядом с существующей (с любой стороны но один раз)). Отсюда и k+1. Пока не вижу как построить рекурсивную цепь рассуждений. Четность и нечётность может быть встречена, на каждом шаге, при снижении длины записи, в любой последовательности.
Ещё интересно, что некоторые каркасы (нечётных n), похоже, не могут дать новых чисел ни при каких условиях, но пока не продумывается.
Может и непродуктивно это всё.
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.