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

Реализация разбиения числа с Динам. Прогр - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Написать программу, которая предлагает пользователю ввести число и выводит в консоль все числа, на которые введенное делится без остатка http://www.cyberforum.ru/cpp-beginners/thread975686.html
Написать программу, которая предлагает пользователю ввести число и выводит в консоль все числа, на которые введенное делится без остатка. использовать только for
C++ Написать программу, которая предлагает пользователю ввести два числа, которые определяют диапазон, вычисляет сумму всех четных чисел и произведение Написать программу, которая предлагает пользователю ввести два числа, которые определяют диапазон, вычисляет сумму всех четных чисел и произведение всех нечетных чисел, входящих в этот диапазон и выводит результаты в консоль. использовать только for. http://www.cyberforum.ru/cpp-beginners/thread975683.html
Написать программу, которая предлагает пользователю ввести число и выводит в консоль его справа налево, то есть перевернув C++
Написать программу, которая предлагает пользователю ввести число и выводит в консоль его справа налево, то есть перевернув. использовать только while
Должно работать, но выдает ошибку C++
#include <iostream> #include <windows.h> using namespace std; class Knuckle{ public: int flag; int x; int y; };
C++ Запись строки в массив http://www.cyberforum.ru/cpp-beginners/thread975678.html
Программой запрашиваются имя, телефон и комментарий: cout<<"Put full name: "; cin>>name; cout<<"Put phone number (only 7 numbers!!): "; cin>>phone; cout<<"Put comments: ";
C++ Вывод массива спиралью Знаю, тема заеженная тема...но...блин, не получается и все. Вводится размер массива (пока что NxN). Вывести натуральные числа спиралькой. вот код: #include "stdafx.h" #include "iostream" #include "conio.h" using namespace std; int n; int s ; подробнее

Показать сообщение отдельно
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
12.10.2013, 21:34     Реализация разбиения числа с Динам. Прогр
как-то так:
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;
 
typedef unsigned long long ULL;
const int MAX_N = 791; // значение установлено опытным путем. результат для 792 уже не влезает в ULL
 
ULL cnt[ MAX_N + 1 ][ MAX_N + 1 ] = { { 0 } };
 
ULL calc( int x, int n )
{
    if ( !x ) return 1;
    if ( x < n ) return 0;
    if ( cnt[ x ][ n ] ) return cnt[ x ][ n ];
 
    ULL sum = 0;
 
    for ( int i = n; i <= x; ++i )
        sum += calc( x - i, i + 1 );
    return cnt[ x ][ n ] = sum;
}
 
int main()
{
    for ( int i = 1; i <= MAX_N; i += 10 )
        cout << i << ": " << calc( i, 1 ) << endl;
 
    return 0;
}
немного поясню. очевидно, что всю работу выполняет ф-ция calc. она принимает число, для которого надо посчитать кол-во разбиений, и наменьшее доступное слагаемое. для каждого рекурсивного вызова это наименьшее слагаемое постоянно возрастает, таким образом учитывается требование про неповторяющиеся слагаемые (каждое следующее слагаемое больше предыдущего).

P.S.: Ах да. функция calc может работать быстрее. она делает много лишней работы. попробуй догадаться как ее ускорить.

Добавлено через 5 минут
Цитата Сообщение от s3lf Посмотреть сообщение
В рунете же мало статей на эту тему.
читай лучше умные книги по алгоритмам
 
Текущее время: 00:13. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru