Алгоритмы на С++
к списку всех задач на массивы
Найти подмножество данного множества чисел такое, что сумма его элементов равна заданному числу.
Решение задачи
|
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 |
void itmathrepetitor_ru() { setlocale(LC_ALL, "Russian"); double *a, s, p; int n, k, ires; bool flag; do { cout << "Введите кол-во элементов множества: "; cin >> n; } while (n<1); // проверка на допустимое значение n a=new double [n]; // выделяем память for (int i=0; i<n; i++) // запрашиваем n чисел { cout << "Введите "<<(i+1)<<" элемент : "; cin >> a[i]; flag=false; //www.itmathrepetitor.ru for (int j=0; j<i; j++) // проверка на повтор { if (a[i]==a[j]) // нашли повтор { flag=true; break; } } if (flag) // если повтор был { cout<<"Такой элемент уже есть в множестве"<<endl; i--; } } cout<<"Введите сумму чисел: "; cin>>s; //www.itmathrepetitor.ru cout<<"Множество: "<<endl; // показ множества for (int i=0; i<n; i++) cout<<a[i]<<" "; cout<<endl; ires=-1; k=powf(2,n); // количество подмножеств for (int i=0; i<k; i++) // перебор подмножеств { p=0; flag=false; for (int j=0; j<n; j++) // перебираем числа из подмножества if (i & (1<<j)) { p+=a[j]; // накапливаем сумму flag=true; // подмножество не пусто } if (p==s && flag) // если сумма совпала и подмножество не пусто { ires=i; break; //www.itmathrepetitor.ru } } if (ires==-1) { cout<<"Подмножество с данной суммой не существует"<<endl; } else { cout<<"Подмножество с данной суммой:"<<endl; for (int j=0; j<n; j++) if (ires & (1<<j)) { cout<<a[j]<<" "; } cout<<endl; //www.itmathrepetitor.ru } delete [] a; // удаляем память } |