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

Задача на динамику или комбинаторику - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Деление дробей. http://www.cyberforum.ru/cpp-beginners/thread341056.html
Задача: вывести в порядке возрастания все правильные несократимые дроби со знаменателем, не превосходящим n. Сам код: #include <iostream> #include <string> using namespace std; using std::string; int main() { int n,i,num,numi; float last=0,min; string temp;
C++ Задача:Определить повторяются Цифры в Числе или нет... Нужно ввести число и в результате получить сообщение повторяются цифры в числе или нет.Способ определения может быть любым. Число нужно вводить полностью(не через пробел :) http://www.cyberforum.ru/cpp-beginners/thread341055.html
Синтаксис- непонятные знаки C++
Что значат знаки: ? и :
Инкремент и вывод на консоль. Непонятное. C++
Объясните, пожалуйста, почему, если так: int i = 5; cout << i << " "; cout << ++i << "\n";, то на консоль выводится всё правильно: 5 6. А если расположить так: int i = 5; cout << i << " " << ++i << "\n";, то выводится: 6 6?
C++ файл.txt http://www.cyberforum.ru/cpp-beginners/thread341006.html
как сделать так чтобы при записи в файл *.txt текст писался на новой строке? Вот на пример вот так: 1)number name 2)number name А не так как у меня 1)number name 2)number name
C++ нубовопросы У меня вопрос, связанный с циклами. Допустим, нужно суммировать числа от 1 до 10 и в итоге получится 55. Для это сделаем { int sum = 0, val = 1; while ( val <= 10 ) sum += val; ++val; } Теперь вопрос: подробнее

Показать сообщение отдельно
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
11.08.2011, 16:27     Задача на динамику или комбинаторику
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
удачи тебе в поисках "хорошего" алгоритма...
Удача пригодилась =)
Таки я был прав, треугольник Паскаля рулит!
К сожалению, понятно объяснить вряд ли смогу, сам только сегодня его строить научился, но тем не менее код проходит все тесты практически мгновенно.
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
int main(){
    
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    
    //строим треугольник паскаля
    int pas[33][33] = {};
    pas[0][0] = 1;
    for (int i = 0; i < 33; ++i)
    {
        pas[i][0] = 1;
        pas[i][i] = 1;
        for (int j = 1; j < i ; ++j)
        {
            pas[i][j] = pas[i-1][j-1] + pas[i-1][j];
        }
    }
    
    int n, k;
    std::cin >> n >> k;
    std::string bin;
    
    //переводим число в двоичное представление
    for ( ; n; n >>= 1)
        bin.push_back( (n & 1) + '0');
    
    //подсчитываем количество сочетаний (количество разрядов - 1) по k
    
    int result = 0;
    
    for (size_t i = k + 1; i < bin.size(); ++i)
    {
        result += pas[i-1][k];
    }
    
    //отдельно рассматриваем случай с последним разрядом...
    int zerocount = 0;
    for (int i = bin.size() - 2; i >= 0 && zerocount <= k; --i)
    {
        if (bin[i] == '1')
        {
            if (k - zerocount - 1 >= 0)
            {
                result += pas[i][k - zerocount - 1];
            }
        }
        else
            ++zerocount;
    }
 
    if (zerocount == k)
        ++result;
 
 
    std::cout << result << std::endl;       
}
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru