Всем привет. Туплю над задачкой все выходные.
- Дано натуральное число N. Выбрать некоторое подмножество позиций так, чтобы находящиеся на них цифры числа (в том порядке, как они записаны) образовывали максимальное число Фибоначчи, которое возможно получить при такой операции.
Условие слегка по-индийски конечно описано, поэтому если кто не понял, разъяснение на примере:
пусть введено число 8359. нужно перебрать все возможные варианты составления других чисел, но чтобы не образовывались инверсии. Все возможные варианты чисел таковы:
- когда убираем одну цифру
8359 => 835 (убираем 9)
8359 => 839 (убираем 5)
8359 => 859 (убираем 3)
8359 => 359 (убираем 8)
когда убираем 2 цифры
8359 => 83 (убираем 5 и 9)
8359 => 89 (убираем 3 и 9)
8359 => 59 (убираем 8 и 3)
8359 => 85 (убираем 3 и 9)
8359 => 39 (убираем 8 и 5)
8359 => 35 (убираем 8 и 9)
когда убираем 3 цифры
8359 => 8 (убираем 359)
8359 => 9 (убираем 835)
8359 => 3 (убираем 859)
8359 => 5 (убираем 839)
причём варианты 853 или например 98 не подойдут, потому что в 853 тройка не может стоять перед пятёркой, а в 98 девятка перед восьмёркой
вот что накатал я (С++):
Код:
#include <iostream>
using namespace std;
unsigned int N, s = 0, a, j=1, c, tmp = 0, m = 10, f0 = 0, f1 = 1, f2, f, k; // N - вводимое число; a - число N для нахождения количества цифр (чтобы не потерять N); s - количество цифр в числе;
int main ()
{
cin >> N; // пользователь вводит нужное число N;
a = N; // сохраняем его в a;
while (a > 0) { // находим
a /= 10; // количество
s ++; // цифр
} // в числе;
a = N; // вновь сохраняем это число
for (int i=s; i>=1; i--) { // цикл от количества цифр в числе до единицы
a /= 10;
c = a*j + tmp;
tmp = N % m;
m *= 10;
j *= 10;
while (f1 <= c) { // заводим цикл для чисел Фибоначчи
f = f1;
f1 = f1 + f0;
f0 = f;
//cout << f1 << ' ';
if (c==f1) // сравниваем число, которое у нас получилось в цикле for с числом фибоначчи
cout << c;
}
f0 = 0; // откатываем числа Фибоначчи до 0-го и 1-го
f1 = 1;
}
return 0;
}
я вот пока что получаю только те числа, в которых удаляется одна цифра. как мне получить все возможные числа в общем виде? (когда удаляется от одной до (s-1) цифры)