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

Задачи для тренировки и лучшего понимания - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Возможно переписать программу? http://www.cyberforum.ru/cpp/thread153534.html
Есть программа Upgrade UA.exe хочу запустить ее на windows mobile 6. Возможно ли ее переписать.
C++ scanf Пусть нужно читать из текста слова, пропуская все символы, кроме a-z и A-Z. То есть из текста Hello, world! ololo O_o получить только Hello world ololo O o Меня интересует, можно ли это... http://www.cyberforum.ru/cpp/thread153153.html
C++ Вернуть stdin в консоль
Допустим я перенаправил поток stdin/stdout в файл с помощью функции freopen. Как заставить его снова работать с консолью? Добавлено через 9 минут Нашел. #include <cstdlib> #include <stdio.h>...
Прошу помочь.Подключение dll на неуправляемом С/С++ C++
Возникла проблема.Есть рабочая dll, необходимо подключить к CLR приложению. Подключение происходит нормально. Все функции работают нормально кроме одной(хотя dll проверял все работает в обычных...
C++ Не сразу закрывающаяся программа http://www.cyberforum.ru/cpp/thread152799.html
Есть команды в терминале.. вроде telnet или sql, эти программы запускаешь и они остаются открытыми пока не дашь команду, например, quit. Во время работы программы она показывает знак приглашения...
C++ Парсер на С вопшем есть файл с текстом..... в етом файле есть какие даные(мусор)...и есть дни: Понедельник,Вторник,среда......с етого файла нада вывести ети дни в порядке нахождениэ... ето походу несложная... подробнее

Показать сообщение отдельно
Хохол
Эксперт С++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
03.08.2010, 00:03
Mr.X, Accepted

Добавлено через 2 минуты
Мои решения
Раз решение
Тупая рекурсия.
O(2^n)
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
#include <fstream>
#include <cmath>
 
using namespace std;
 
#ifdef ONLINE_JUDGE
#include <iostream>
#else
ifstream cin("input.txt");
ofstream cout("output.txt");
#endif
 
int ar[20];
int n, mi = 987654321, sum = 0;
 
void p(int pos, int curSum)
{
    if(pos == n)
        mi = min(mi, abs(sum - 2*curSum));
    else
    {
        p(pos+1,curSum);
        p(pos+1,curSum+ar[pos]);
    }
}
 
int main()
{   
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> ar[i];
        sum += ar[i];
    }
    p(0,0);
    cout << mi;
}

Два решение
Те же яйца, только без рекурсии.
O(n * 2^n)
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
#include <fstream>
#include <cmath>
 
using namespace std;
 
#ifdef ONLINE_JUDGE
#include <iostream>
#else
ifstream cin("input.txt");
ofstream cout("output.txt");
#endif
 
int ar[20];
int n, mi = 987654321;
 
int f(int x)
{
    int sum1 = 0, sum2 = 0;
    for(int i = 0; i < n; i++)
        if(x & (1<<i))
            sum1 += ar[i];
        else
            sum2 += ar[i];
    return abs(sum1 - sum2);
}
 
int main()
{   
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> ar[i];
    for(int i = 0; i < (1<<n); i++)
        mi = min(mi, f(i));
    cout << mi;
}

Три решение
Простенькая динамика
O(n*W), где W - максимальная возможная сумма весов.
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
#include <fstream>
#include <cmath>
 
using namespace std;
 
#ifdef ONLINE_JUDGE
#include <iostream>
#else
ifstream cin("input.txt");
ofstream cout("output.txt");
#endif
 
int ar[20];
bool v[3000000];
int n, mi = 987654321, sum = 0;
 
int main()
{   
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> ar[i];
        sum += ar[i];
    }
    v[0] = true;
    for(int i = 0; i < n; i++)
        for(int j = sum; j >= 0; j--)
            if(v[j])
                v[j+ar[i]] = true;
    for(int i = 0; i <= sum; i++)
        if(v[i])
            mi = min(mi, abs(sum-2*i));
    cout << mi;
}
5
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru