Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
0 / 0 / 0
Регистрация: 15.09.2016
Сообщений: 10
1

Задача на рекурсию

29.12.2016, 15:59. Просмотров 975. Ответов 19
Метки нет (Все метки)

Нашел одну задачу, она по моему на рекурсию, но не могу реализовать это.

Сколько существует чисел от 1 до n, таких, что цифры числа начиная с самого старшего разряда, составляют неубывающую послеовательность?

ВВОД
20
ВЫВОД
18

от 1 до 20 есть два числа которые не соответствуют условию, это 10 и 20
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.12.2016, 15:59
Ответы с готовыми решениями:

Задача на рекурсию
Задание: написать функцию умножения двух чисел, используя только операции сложения и рекурсии. Не...

Задача на рекурсию
С помощью рекурсии вычислить произведение ненулевых элементов динамического массива. Кто-то знает?...

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

Задача на рекурсию
Дано число. Вывести все цифры этого числа, не используя дополнительных библиотек, массивов, списков...

19
Эксперт С++
1929 / 1041 / 109
Регистрация: 29.03.2010
Сообщений: 3,167
29.12.2016, 16:06 2
та не... тут вроде рекурсия нафиг не впала....


тупо в цикле перебираете от единицы до n
дальше проверка, число удовлетворяет "условию" если да - икрементим счетчик.

ИМХО рекурсией тут и не пахнет...
0
Форумчанин
Эксперт CЭксперт С++
8149 / 4999 / 1436
Регистрация: 29.11.2010
Сообщений: 13,460
29.12.2016, 16:07 3
n как-то ограничена?
0
0 / 0 / 0
Регистрация: 15.09.2016
Сообщений: 10
29.12.2016, 16:09  [ТС] 4
Извините, забыл дописать, n до 10^18

Добавлено через 1 минуту
n до 10^18
0
Форумчанин
Эксперт CЭксперт С++
8149 / 4999 / 1436
Регистрация: 29.11.2010
Сообщений: 13,460
29.12.2016, 16:09 5
Решение в лоб:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <algorithm>
#include <iostream>
#include <string>
#include <cstddef>
 
int main()
{
    uint64_t x, counter = 0;
    std::cin >> x;
    for (uint64_t i = 1; i <= x; i++)
    {
        const std::string tmp = std::to_string(i);
        if (std::is_sorted(tmp.begin(), tmp.end()))
            counter++;
    }
    std::cout << counter;
}
Но тут явно можно математически решить.
0
4341 / 2007 / 255
Регистрация: 01.03.2013
Сообщений: 5,391
Записей в блоге: 22
29.12.2016, 16:12 6
Цитата Сообщение от Maxim Prishchepa Посмотреть сообщение
ИМХО рекурсией тут и не пахнет...
кто не чувствует в подобных задачах легкий и едва уловимый божественный аромат рекурсии, тот или тупо брутфорсит в цикле (как вы предлагаете) 100500 лет, либо он Дональд Кнут и переписывает рекурсивный алгоритм в итеративном стиле через собственный велосипедный стек и типы данных, фактически эмулируя ту же самую рекурсию

Добавлено через 51 секунду
ЗЫ ага, вот теперь и перебирайте в цикле
Цитата Сообщение от SAdlet Посмотреть сообщение
Извините, забыл дописать, n до 10^18
0
Эксперт С++
1929 / 1041 / 109
Регистрация: 29.03.2010
Сообщений: 3,167
29.12.2016, 16:15 7
Цитата Сообщение от _Ivana Посмотреть сообщение
тупо брутфорсит в цикле (как вы предлагаете) 100500 лет
все норм, это для MVP, а дальше 100500 часов на оптимизацию запросим
0
Форумчанин
Эксперт CЭксперт С++
8149 / 4999 / 1436
Регистрация: 29.11.2010
Сообщений: 13,460
29.12.2016, 16:25 8
Тут можно заметить, что увеличивая десяток, мы имеем на n чисел с убывающими цифрами больше.
n < 10 => 0
n < 20 => 0+1 = 1
n < 30 => 0+1+2 = 3
n < 40 => 0+1+2+3 = 6
n < 50 => 0+1+2+3+4 = 10

Добавлено через 3 минуты
C++
1
2
3
4
int foo(const int n)
{
    return n ? foo(n-1) + n : 0;
}
0
270 / 129 / 43
Регистрация: 05.02.2015
Сообщений: 803
29.12.2016, 16:25 9
ну это работает только до 100.
0
Форумчанин
Эксперт CЭксперт С++
8149 / 4999 / 1436
Регистрация: 29.11.2010
Сообщений: 13,460
29.12.2016, 16:39 10
Цитата Сообщение от minore Посмотреть сообщение
ну это работает только до 100.
Да, но эта задача явно на рекурсию. Думаю, что скоро появится решение от мастера рекурсий _Ivana
А у меня мозг ещё не настолько модифицировался от хаскеля (в хорошую сторону, разумеется).
0
4341 / 2007 / 255
Регистрация: 01.03.2013
Сообщений: 5,391
Записей в блоге: 22
29.12.2016, 23:23 11
Обещанный каминг сун Без особых причесываний, навскидку (спешу на свидание )
Работает, как тот ёжик:
- Ежик, тебе чего?
- Фамилию хочу сменить
- А какая у тебя фамилия?
- Быстрый!
- А какую хочешь?
- Вщьюхххх!

для полного вщьюха можно было бы замемоизировать результаты рекурсивных функций, но для стартовых значений аргументов имхо и так неплохо получилось
Да, представление числа в массив по десятичным разрядам осилите самостоятельно.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef unsigned long long int ull;
 
//int m[] = {2,0}, ms = sizeof(m)/sizeof(m[0]);
int m[] = {7,6,4,5,1,3,7,3,7,6,5,7,8,9,4,3,6,5}, ms = sizeof(m)/sizeof(m[0]);
 
ull h(int d, int n) {
    if (n==0) return 1;
    else {
        ull r = 0;
        for (int j=d; j<10; j++) r += h(j,n-1);
        return r;
    }
}
ull f(int d, int i) {
    if (d>m[i]) return 0;
    else if (i==ms-1) return m[i]-d+1;
    else {
        ull r = 0;
        for (int j=0; j<m[i]; j++) r += h(j,ms-i-1);       
        return r + f(m[i],i+1);
    }
}
int main() { cout << f(0,0)-1; }
UPD: есть вероятность, что кота надо чуть допилить - но это уже попозже

Добавлено через 16 минут
Допилка очепятки - в строке 19 надо
C++
1
for (int j=d;
1
270 / 129 / 43
Регистрация: 05.02.2015
Сообщений: 803
30.12.2016, 01:37 12
а вот такой вариант вообще без цикла?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std;
bool inchek (long a, long b)
{
if (a ==0)
return true;
if (a <b && a%10 <b)
return false;
inchek(a/10, a%10);
}
long summ_  (long a, long b)
{
if (a <10)
return b;
if (inchek(a/10, a%10))
b = summ_(a -1, b +1);
else
b = summ_(a -1, b);
}
int main ()
{
long n, count;
cin >> n;
count =summ_(n, 0);
cout << count;
return 0;
}
0
4341 / 2007 / 255
Регистрация: 01.03.2013
Сообщений: 5,391
Записей в блоге: 22
30.12.2016, 01:47 13
minore, считает долго и результат не совпадает с моими котами.

ЗЫ если кому-то интересно, могу переписать и свое решение совсем без циклов.
0
270 / 129 / 43
Регистрация: 05.02.2015
Сообщений: 803
30.12.2016, 02:23 14
да, согласен. с условиями напутал в первой функции: сейчас вручную до 200 посчитал, должно совпасть, так это?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;
bool inchek(long a, long b, bool flag)
{
if (a == 0)
return flag;
if (a % 10 >b)
inchek(a / 10, a % 10, false);
else
inchek(a / 10, a % 10, true);
}
long summ_(long a, long b)
{
if (a <10)
return b;
if (inchek(a / 10, a % 10, false))
b = summ_(a - 1, b + 1);
else
b = summ_(a - 1, b);
}
int main()
{
long n, count;
cin >> n;
count = summ_(n, 0);
cout << count;
return 0;
}
Добавлено через 7 минут
можно без третьего параметра:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;
bool inchek(long a, long b)
{
if (a % 10 >b)
return false;
if (a < b)
return true;
 
inchek(a / 10, a % 10);
}
long summ_(long a, long b)
{
if (a <10)
return b;
if (inchek(a / 10, a % 10))
b = summ_(a - 1, b + 1);
else
b = summ_(a - 1, b);
}
int main()
{
long n, count;
cin >> n;
count = summ_(n, 0);
cout << count;
return 0;
}
0
4341 / 2007 / 255
Регистрация: 01.03.2013
Сообщений: 5,391
Записей в блоге: 22
30.12.2016, 02:26 15
Цитата Сообщение от minore Посмотреть сообщение
сейчас вручную до 200 посчитал, должно совпасть, так это?
ваш summ_(20, 0) выдает 9 - как можно так вручную посчитать? Держите тупую тестирующую функция, если вам лень ее написать:
C++
1
2
3
4
5
6
7
8
9
10
int good(ull n) {
    int d = 100;
    while (n>0) {
        if (n%10 > d) return 0;
        d = n%10;
        n /= 10;
    }
    return 1;
}
ull g(ull n) { ull r=0; for (ull i=1; i<=n; i++) r+=good(i); return r; }
0
270 / 129 / 43
Регистрация: 05.02.2015
Сообщений: 803
30.12.2016, 02:29 16
так 9 и должно быть разве нет? 11 12 13 14 15 16 17 18 19? или 11 мы не считаем?
0
4341 / 2007 / 255
Регистрация: 01.03.2013
Сообщений: 5,391
Записей в блоге: 22
30.12.2016, 02:31 17
В стартовом посте есть пример, который как бы намекает, что имеет в виду автор задачи.
0
270 / 129 / 43
Регистрация: 05.02.2015
Сообщений: 803
30.12.2016, 02:44 18
ну одну строку заменить - и одноразрядные числа будут включены:
было:
C++
1
if (a <10)
станет
C++
1
if (a <=0)
и будут учитывания одноразрядных чисел. меня вот больше смущает, что больше 5000 в моей проге переполнение идет.

с этим пока что делать не знаю.
0
Любитель чаепитий
3266 / 1559 / 484
Регистрация: 24.08.2014
Сообщений: 5,397
Записей в блоге: 1
30.12.2016, 11:05 19
Цитата Сообщение от _Ivana Посмотреть сообщение
ЗЫ если кому-то интересно, могу переписать и свое решение совсем без циклов.
Покорнейше прошу.
0
4341 / 2007 / 255
Регистрация: 01.03.2013
Сообщений: 5,391
Записей в блоге: 22
31.12.2016, 00:32 20
Смотрим на исходного кота - видим 2 места использования цикла: строки 9-11 и 18-20. В обоих местах нам не нужны собственно циклы (они вообще никогда, собственно, не нужны ), а нужно замапредьюсить диапазон аргументов через чистую функцию h по моноиду Sum - то есть попросту получить сумму значений чистой функции по диапазону аргумента. Чтобы не связываться с stl и ее контейнерами (что можно было сделать) а также с лямбдами (что также можно сделать), накостылим простейший вариант вспомогательной функции s, которая возвращает сумму значений функции h на переданном диапазоне, и потом заменим расчет результата через циклы вызовом этой функции - см. предыдущего кота с циклами и нового шелковистого без циклов : в результате оформления расчетов через дополнительную функцию стало возможным заменить ифы на лаконичные тернарные операторы, уменьшилось число строк, повысилась понятность, да и кот теперь один в один переносится на любой функциональный язык программирования как есть

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef unsigned long long int ull;
 
//int m[] = {2,0}, ms = sizeof(m)/sizeof(m[0]);
int m[] = {7,6,4,5,1,3,7,3,7,6,5,7,8,9,4,3,6,5}, ms = sizeof(m)/sizeof(m[0]);
 
ull h(int d, int n);
ull s(int a, int b, int n) {return a>b ? 0 : h(a, n) + s(a+1, b, n); }
 
ull h(int d, int n) { return n==0 ? 1 : s(d, 9, n-1); }
 
ull f(int d, int i) {
    return d>m[i] ? 0 : i==ms-1 ? m[i]-d+1 : s(d,m[i]-1,ms-i-1) + f(m[i],i+1); }
 
int main() { cout << f(0,0)-1; }
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
31.12.2016, 00:32

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Задача на рекурсию
Помогите решить след. задачу: Вот мой вариант, но здесь не сохраняется порядок: void Func()...

Задача на рекурсию
Вот код проги которую я написал: #include &lt;iostream&gt; using namespace std; int factr(double...

Задача на рекурсию
Всем доброго времени суток. Прошу подсказать мне условие задачи на рекурсию(нам дали задание самим...

Задача на рекурсию
помогите написать пожалуйста программу на с++ по теме рекурсия. Задано действительное A, найти...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.