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

Рекурсия (алгоритм подсчета числа способов, с помощью которых можно представить число М в виде суммы) - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Задача массива! http://www.cyberforum.ru/cpp-beginners/thread805897.html
Помогите пожалуйста с такой задачой : Написать программу, которая: • Выводит текст на экран дисплея; • Определение в каждом предложении текста количество символов, отличных от букв и пропуска; •...
C++ Использовать представление графа в виде списков смежности добавить в орграф новую вершину Народ меня тут 11 задач мне нужно их подробно прокомментировать какая строчка что делает(пример первая задача) помогите плиз кому не сложно хотя бы по одной задачке буду очень благодарен задача... http://www.cyberforum.ru/cpp-beginners/thread805895.html
C++ Использовать представление графа в виде списков смежности вывести на экран все вершины, не смежные с данной
Народ меня тут 11 задач мне нужно их подробно прокомментировать какая строчка что делает(пример первая задача) помогите плиз кому не сложно хотя бы по одной задачке буду очень благодарен задача...
По входной последовательности построить идеально сбалансированное дерево C++
Народ меня тут 11 задач мне нужно их подробно прокомментировать какая строчка что делает(пример первая задача) помогите плиз кому не сложно хотя бы по одной задачке буду очень благодарен Задача 9...
C++ По входной последовательности построить дерево бинарного поиска и найти количество узлов, имеющих только одного левого потомка http://www.cyberforum.ru/cpp-beginners/thread805886.html
Народ меня тут 11 задач мне нужно их подробно прокомментировать какая строчка что делает(пример первая задача) помогите плиз кому не сложно хотя бы по одной задачке буду очень благодарен Задача 8...
C++ Списки. Удалить каждое последующее вхождение символа если он встречался до этого. Народ меня тут 11 задач мне нужно их подробно прокомментировать какая строчка что делает(пример первая задача) помогите плиз кому не сложно хотя бы по одной задачке буду очень благодарен Задача 7... подробнее

Показать сообщение отдельно
Kastaneda
Форумчанин
Эксперт С++
4655 / 2863 / 228
Регистрация: 12.12.2009
Сообщений: 7,275
Записей в блоге: 2
Завершенные тесты: 1
12.03.2013, 21:14
вот самый медленный способ
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
 
int calc (int m, int n)
{
    if ( m < 0 ) {
        return 0;
    }
    if ( m <= 1 || n == 1 ) {
        return 1;
    }
 
    return calc (m, n - 1) + calc (m - n, n); 
}
 
int main ()
{
    int M, N;
    std::cin >> M >> N;
 
    std::cout << calc (M, N) << std::endl;
 
    return 0;
}
а вот быстрее, с запоминанием посчитанных значений
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
29
30
31
32
33
34
35
36
37
38
#include <iostream>
 
#define SIZE 100
 
int arr[SIZE][SIZE];
 
int calc (int m, int n)
{
    if ( m >= 0 && m >= 0 && arr[m][n] > 0 ) {
        return arr[m][n];
    }
    if ( m < 0 ) {
        return 0;
    }
    if ( m <= 1 || n == 1 ) {
        return 1;
    }
 
    arr[m][n] =  calc (m, n - 1) + calc (m - n, n); 
 
    return arr[m][n];
}
 
int main ()
{
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            arr[i][j] = -1;
        }
    }
 
    int M, N;
    std::cin >> M >> N;
 
    std::cout << calc (M, N) << std::endl;
 
    return 0;
}
в этом случае M и N должны быть не больше SIZE (можно сделать динамический массив, тогда M и N будут ограничены размером ОЗУ).
Можно еще ускорить, если вставить код массив с предпосчитанными значениями, но это если есть острая необходимость.
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru