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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Теория плагинов http://www.cyberforum.ru/cpp/thread123914.html
Всем привет. Для одной моей проги, нужно реализовать поддержку плагинов. Плагины предполагаются простенькие, написанные на Си. То, что плагин, это просто .so файл - понятно. То, что прога может дергать из .so файла функции - тоже понятно. 1. Непонятно то, как сам плагин сможет дергать функции из программы? 2. Программа написана на С++, но плагины предполагаю писать на Си, во избежания...
C++ ./massdown: /usr/lib/libstdc++.so.6: version `GLIBCXX_3.4.11' not found (required by ./massdown) всем хай! собираю свою программу на новом железе х86_64 долго не получалось скомпилить. при линковке получал вот такое сообщение: relocation R_X86_64_32 against `a local symbol' я так понял, это из-за того что часть библиотек от которых зависит цель, были собраны как 32-ух битные. но с этим вроде все нормально, пересобрал все либы - скомпилировалось. теперь при запуске получаю такое... http://www.cyberforum.ru/cpp/thread98890.html
Как понять этот константный указатель? C++
В общем, имеется класс Cat. Объект класса - SimpleCat. И имеется функция с константым указателем: const SimpleCat* const FunctionTwo(const SimpleCat* const theCat) Что обозначают все эти const? Насколько я понимаю: 1. Константный указатель. 2. Может ссылаться только на FunctionTwo 3. Ничего не изменяет в объекте. 4. Ничего не делает с объектом theCat.
C++ Перехват и подмена вызываемых функций
Здравствуйте. Нужно подменить вызов таких функций как open(), lstat(), stat(), read(), write(), mkdir(), chdir(), getcwd() для определенного процесса. Интересует мнение других. Как бы вы реализовали эту задачу. Спасибо!

Показать сообщение отдельно
Mr.X
Эксперт С++
 Аватар для Mr.X
3011 / 1667 / 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;
}
 
Текущее время: 21:16. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru