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

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

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

Показать сообщение отдельно
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4237 / 2770 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 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 будут ограничены размером ОЗУ).
Можно еще ускорить, если вставить код массив с предпосчитанными значениями, но это если есть острая необходимость.
 
Текущее время: 14:32. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru