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

Задачи для тренировки и лучшего понимания - 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++ Парсер на С вопшем есть файл с текстом..... в етом файле есть какие даные(мусор)...и есть дни: Понедельник,Вторник,среда......с етого файла нада вывести ети дни в порядке нахождениэ... ето походу несложная... подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
02.08.2010, 23:56
Цитата Сообщение от Хохол Посмотреть сообщение
Mr.X, алгоритм скорее всего верен, все мои тесты программа прошла
Но. В оригинале решение должно укладываться в 2 секунды. У вас же асимптотика O(n! * n), что очень много, и уже при n = 11 работает долго (На тимусе же у вас Time Limit Exceeded #1).
Предлагаю придумать более оптимальное решение.
Да, медленно работает, но я в первом варианте за скоростью и не гнался. Надо будет покумекать.

Добавлено через 5 часов 54 минуты
Более быстрое решение с камнями
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
//////////////////////////////////////////////////////////////////////////////////////
//У вас есть несколько камней известного веса W1, …, Wn. Напишите программу, 
//которая распределит камни в две кучи так, что разность весов этих двух куч 
//будет минимальной.
//Исходные данные
//Ввод содержит количество камней N (1 <= N <= 20) и веса камней
//W1, …, Wn (1 <= Wi <= 100 000) — целые, разделённые пробельными символами.
//Результат
//Ваша программа должна вывести одно число — минимальную разность весов двух куч.
//Пример:
//исходные данные
//5
//
//5
//8
//13
//27
//14
//результат
//3
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cmath>
#include <ctime>
#include <iostream>
#include <numeric>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
const size_t  MAX_STOUN_COUNT = 20;
//////////////////////////////////////////////////////////////////////////////////////
typedef double                 T_weight;
typedef std::vector<T_weight>  T_weights;
typedef unsigned long          T_uns;
//////////////////////////////////////////////////////////////////////////////////////
T_weight  get_min_weight_diff(T_weights  weights)
{
    clock_t  cstart  = clock();    
    std::sort(weights.begin(), weights.end());
    T_weight  common_weight_half 
        = std::accumulate(weights.begin(), weights.end(), T_weight()) / 2;    
    T_uns     i_pred            = 0;
    T_weight  sum               = 0;
    T_weight  min_diff          = 0;
    bool      min_diff_is_init  = false;
    for(T_uns i = 0; i < (1U << (weights.size() - 1)) ; ++i)
    {       
        T_uns  i_temp  = i;        
        T_uns  mask    = i ^ i_pred;
        T_uns  pos     = 0;
        while(mask)
        {
            if(mask & 1)
            {
                if(i_temp & 1)
                {
                    sum += weights[pos];
                }
                else            
                {
                    sum -= weights[pos];
                }            
            }
            mask   >>= 1;
            i_temp >>= 1;
            ++pos;
        }
        T_weight  cur_diff = abs(sum - common_weight_half) * 2;
        if(   !min_diff_is_init
           || cur_diff < min_diff)
        {            
            min_diff = cur_diff;
            min_diff_is_init = true;
        }
        i_pred = i;        
    }
    clock_t cend = clock();
    double millis = 1000.0 * (cend - cstart) / CLOCKS_PER_SEC;
    std::cout << std::endl
              << "Время выполнения функции " 
              << millis 
              << " миллисекунд."
              << std::endl;
    return  min_diff;
}
//////////////////////////////////////////////////////////////////////////////////////
struct  T_input_weight
{
    int ind_;
    T_input_weight() : ind_(0)
    {}
    void operator() (T_weight&  weight)
    {
        std::cout << "вес камня № "
                  << ++ind_
                  << " = ";
        std::cin >> weight;
    }
};
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    int n;
    do
    {
        std::cout << "Введите количество камней: ";
        std::cin >> n;
    }while(MAX_STOUN_COUNT < n);   
    T_weights  weights(n);
    std::for_each(weights.begin(), weights.end(), T_input_weight());
    std::cout << "Минимальная разность весов двух куч этих камней равна: "
              << get_min_weight_diff(weights)
              << std::endl;
    return 0;
}
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru