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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
#1

Рекурсия, перебор. Сложность 70%. Резисторы - C++

22.07.2013, 14:32. Просмотров 535. Ответов 0
Метки нет (Все метки)

Резисторы
(Время: 1 сек. Память: 16 Мб Сложность: 59%)
Радиолюбитель Петя решил собрать детекторный приемник. Для этого ему понадобился конденсатор емкостью C мкФ. В распоряжении Пети есть набор из n конденсаторов, емкости которых равны C1, C2, ... ,Cn соответственно. Петя помнит, как вычисляется емкость параллельного соединений двух конденсаторов (Cnew = C1 + C2) и последовательного соединения двух конденсаторов (Cnew = (C1*C2)/(C1+C2) ). Петя хочет спаять некоторую последовательно-параллельную схему из имеющегося набора конденсаторов, такую, что ее емкость ближе всего к искомой (то есть абсолютная величина разности значений минимальна). Разумеется, Петя не обязан использовать для изготовления схемы все конденсаторы.

Напомним определение последовательно-параллельной схемы. Схема, составленная из одного конденсатора, - последовательно-параллельная схема. Любая схема, полученная последовательным соединением двух последовательно-параллельных схем, - последовательно-параллельная, а также любая схема, полученная параллельным соединением двух последовательно-параллельных схем, - последовательно-параллельная.

Входные данные

В первой строке каждого входного файла INPUT.TXT заданы числа n и C. Во второй строке содержится последовательность емкостей имеющихся в наличии конденсаторов C1, C2, ..., Cn. Значения всех емкостей - вещественные числа. Для всех входных файлов n < 7.

Выходные данные

В выходной файл OUTPUT.TXT необходимо вывести YES, если Пете удастся собрать схему, емкость которой отличается не более чем на 0.01 от требуемого значения C. В противном случае следует вывести NO.

Пример

№ INPUT.TXT OUTPUT.TXT
1 3 1.66
1 2 1 YES
Пояснения к примеру

Последовательно соединим первый и второй конденсаторы, а затем полученную схему соединим параллельно с третьим. Полученная схема будет иметь емкость 1.(6)

Я сначала не дочитав условие сделал простой перебор где добавлял +1 в цепь. Но потом, получив ВА 5. Понял, тут можно делать схемы например
5=2+2+1 или 5=2+3 или 5=3+1+1 что-то в этом роде.
Так вот, рекурсию никак не могу придумать как написать из-за этих кучек. Неужели остается только все кучки сделать???
Вот мой код(ВА 5)
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
#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <fstream>
 
using namespace std;
 
int main()
{
ifstream cin ("input.txt");
ofstream cout ("output.txt");
int n;
double c;
cin >> n >> c;
queue < double > o;
queue < set < int > > check;
set < int > s;
vector < double > v;
 
for (int i=0;i<n;i++)
{
    double x;
    cin >> x;
    v.push_back(x);
}
 
for (int i=0;i<n;i++)
{
    for (int j=i+1;j<n;j++)
    {
        s.insert(i);
        o.push(v[i]+v[j]);
        s.insert(j);
        check.push(s);
        o.push((v[i]*v[j])/(v[i]+v[j]));
        check.push(s);
        s.erase(i);s.erase(j);
    }
}
bool ans=false;
while (true)
{
s=check.front();
double c1=o.front();
if (c1==c || abs(c-c1)<=0.01){
                              ans=true;
                              break;
                              }
o.pop();check.pop();
for (int i=0;i<n;i++)
{
    if (s.find(i)!=s.end())
    {
                           continue;
    }
    else {
        o.push(v[i]+c1);
        s.insert(i);
        check.push(s);
        o.push((v[i]*c1)/(v[i]+c1));
        check.push(s);
        s.erase(i);
        }
}
if (o.empty())
  break;
}
if (ans==true){
               cout << "YES" << endl;
               }
else {
     cout << "NO" << endl;
     }
//system("PAUSE >> void");
return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.07.2013, 14:32     Рекурсия, перебор. Сложность 70%. Резисторы
Посмотрите здесь:

Вычислить величину тока через параллельные резисторы - C++
Составьте программу для вычисления значения силы тока И на участке, состоящем из двух параллельно соединенных резисторов сопротивлением R1...

Сложность алгоритмов - C++
Добрый день, пытаюсь оценить сложность алгоритмов, но возникли сомнения в правильности рассчетов. Собственно рассматриваю два алгоритма -...

Сложность с getline() - C++
Дорогие форумчане! Возникла сложность при использовании getline(). Допустим, у нас есть такой код: int a,b; string s; cin&gt;&gt;a; ...

Неожиданная сложность с read_json() - C++
Всем привет! Возникла следующая непонятка. Через сокет я получаю буфер, содержащий строку {&quot;jsonrpc&quot;:&quot;2.0&quot;,&quot;info_type&quot;:&quot;range&quot;,...

Сложность бинарного поиска - C++
Добрый вечер, решал данную задачу: Девочка загадала число от 1 до N. За какое наименьшее количество вопросов вида «Загаданное тобой...

сложность со структурами и файлами - C++
задание было такое: список муз.дисков: номер, название, кол-во песен, время проигрывания, цена. Распечатать данные про диски, в которых не...

Вычислительная сложность CRC32 - C++
Какова вычислительная сложность алгоритма CRC32? N^2 или NlogN или еще что-то?

Время выполнения(сложность) - C++
Как вычислить время выполнения программы? и что такое NlogN?

Временная сложность алгоритмов - C++
Добрый вечер. Требуется разработать ПО обеспечивающие анализ временной сложности некоторых алгоритмов. Вот возник вопрос: как следует...

Сложность в реализации команды - C++
Программа открывает окно, заголовком которого является командная строка. Обеспечить возможность перетаскивания окна за любую точку его...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru