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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Простые числа http://www.cyberforum.ru/cpp-beginners/thread926986.html
Вывести список простых чисел от 1 ого до млн.(1000000) с помощью решета иратосфена. Помогите решить пож.
C++ valarray Помогите разобраться, в книге есть код: // studentc.h -- defining a Student class using containment #ifndef STUDENTC_H_ #define STUDENTC_H_ #include <iostream> #include <string> #include <valarray> class Student { http://www.cyberforum.ru/cpp-beginners/thread926970.html
Ping по списку адресов с применением system C++
Здравствуйте. Возникла необходимость написать консольную программу, которая проверяет Ping-ом список адресов из файла и записывает результат в другой файл. До этого подобное было реализовано в bat-файле. Мудрить с с++ не стал бы, но для моих нужд bat не подходит. #include <iostream> #include <fstream> using namespace std; string a; //Перегружаем функцию system для удобства...
C++ Приоритет преобразований внутри if
Всем привет. Рассмотрим такой код: #include <iostream> class C { typedef void (C::*fp)() const; public: operator fp() const {
C++ Не могу вызвать функцию из dll С++ в С# в системе Win 7 64bit, MSVS 2008 http://www.cyberforum.ru/cpp-beginners/thread926875.html
Здравствуйте! Уже два дня не могу вызвать функцию из dll C++ в программе, написанная в C#. Программа пишется в MS VS 2008 Win 7 64bit. Сначала опишу С++ проект. Создаю обычное пустое C++ dll приложение. Header файл main.h: // main.h #include <stdio.h> __declspec(dllexport) void Demo();
C++ Коррекция #include <iostream> #include <string> #include <cstring> int main() { using namespace std; char charr; string str; cout << "Lenght of string in charr before input: " << strlen(charr) << endl; подробнее

Показать сообщение отдельно
yutr777
 Аватар для yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
22.07.2013, 14:32     Рекурсия, перебор. Сложность 70%. Резисторы
Резисторы
(Время: 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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 11:31. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru