Войти
ФлеймФорумПрограммирование

Задачка

Страницы: 1 2 3 4 Следующая »
#0
21:23, 2 июня 2017

Девушки на работе проходили какой-то тест, там была задача:

We are given 5 integer numbers.
Write a program that checks if the sum of some subset of them is 0.
and return true if any subset founded has sum=0 else false
Решение требовалось написать на шарпике.
Сперва мне показалось что задачка простая, но потом понял что нифига моя математика пятиклассника тут не потянет.


#1
21:35, 2 июня 2017

Задача нерешаема

#2
21:37, 2 июня 2017

nes
перебираешь все возможные подмножества, проверяешь сумму на ноль. задача называется subset sum problem и является np-complete.

#3
22:12, 2 июня 2017
bool allsubsets(vector<int> v) {
    if(v.empty()) return false;

    size_t max = 1 << v.size();

    for(size_t flag = 1; flag < max; flag++) {

        size_t idx = 0;
        size_t t = flag;
        int res = 0;
        
        while(t) {
            idx++;
            if(t & 1) {
                res += v[idx];
            }
            t >>= 1;
        }

        if(res == 0) return true;
    }

    return false;
}

int main() {

  cout << allsubsets({1,2,3,4,-3}) << endl;

  return 0;
}

Ну что же вы, кармаки.

#4
22:19, 2 июня 2017

Чота мне кажется что тут можно решить математикой, учесть там максимумы и минимумы, но мозгов не хватает.

#5
22:23, 2 июня 2017

nes
> Write a program that checks if the sum of some subset of them is 0
Пустое множество является подмножеством любого множества.
Сумма элементов пустого множества 0 :)

#6
23:10, 2 июня 2017

Решение наверное можно упростить если лишь одно из чисел положительное или отрицательное, тогда перебирать придется лишь оставшиеся числа другого знака.
И то, после проверок на модули, отбрасывая явно нерешаемые комбинации.

#7
23:26, 2 июня 2017
        public static bool FindSum()
        {
            int[] numbers = new[] { 1, 2, 3, -30, 5 };

            int sum = numbers.Sum();

            for (int i = 0; i < 5; i++)
            {
                if (sum - numbers[i] == 0) return true;

                for (int j = 0; j < 5; j++)
                {
                    if (j == i) continue;
                    if (sum - numbers[i] - numbers[j] == 0) return true;

                    for (int k = 0; k < 5; k++)
                    {
                        if (k == i || k == j) continue;
                        if (sum - numbers[i] - numbers[j] - numbers[k] == 0) return true;
                    }
                }
            }
            return false;
        }

не знаю, может затупил, дайте данных для проверки
массив не стал передавать, ибо лень

#8
23:44, 2 июня 2017

если бы задача была сложнее, то я бы решал как то так(псевдокод):

#define @ rand()
vector<int> random_subset(size_t n){vector<int> out;out.push_back(@%n);for(;@;)out.push_back(@%n);return out;}
int sum(const vector<int>&arr,const vector<int>&ids){int v=0;for(size_t i=0;i<ids.size();i++)v+=arr[ids[i]];return v;}
bool check(vector<int> inp){
  for(;@;){if(0==sum(inp,random_subset(inp.size()))return true;}
  return false;
}
а потом просто оптимизировал удачу.

#9
0:53, 3 июня 2017
if a=0 then writeln('a goditsya');
if b=0 then writeln('b goditsya');
if a+b=0 then writeln('a+b goditsya');
if c=0 then writeln('c goditsya');
if a+c=0 then writeln('a+c goditsya');
if b+c=0 then writeln('b+c goditsya');
if a+b+c=0 then writeln('a+b+c goditsya');
if d=0 then writeln('d goditsya');
if a+d=0 then writeln('a+d goditsya');
if b+d=0 then writeln('b+d goditsya');
if a+b+d=0 then writeln('a+b+d goditsya');
if c+d=0 then writeln('c+d goditsya');
if a+c+d=0 then writeln('a+c+d goditsya');
if b+c+d=0 then writeln('b+c+d goditsya');
if a+b+c+d=0 then writeln('a+b+c+d goditsya');
if e=0 then writeln('e goditsya');
if a+e=0 then writeln('a+e goditsya');
if b+e=0 then writeln('b+e goditsya');
if a+b+e=0 then writeln('a+b+e goditsya');
if c+e=0 then writeln('c+e goditsya');
if a+c+e=0 then writeln('a+c+e goditsya');
if b+c+e=0 then writeln('b+c+e goditsya');
if a+b+c+e=0 then writeln('a+b+c+e goditsya');
if d+e=0 then writeln('d+e goditsya');
if a+d+e=0 then writeln('a+d+e goditsya');
if b+d+e=0 then writeln('b+d+e goditsya');
if a+b+d+e=0 then writeln('a+b+d+e goditsya');
if c+d+e=0 then writeln('c+d+e goditsya');
if a+c+d+e=0 then writeln('a+c+d+e goditsya');
if b+c+d+e=0 then writeln('b+c+d+e goditsya');
if a+b+c+d+e=0 then writeln('a+b+c+d+e goditsya');

#10
1:09, 3 июня 2017

Класс. Развернутые циклы, да еще на дельфях. Быстрее быть не может.

#11
1:14, 3 июня 2017

dave
вероятностный алгоритм, вероятность тех или иных вариантов определяет тарас

#12
1:15, 3 июня 2017
+ Показать

upd: полное решение

// http://ideone.com/H2uNwE
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> out;
void f(int N,int L,const vector<int>&prefix){
  auto arr=prefix;
  for(auto i=arr.empty()?0:arr.back()+1;i<N;i++){
    arr.push_back(i);
    if(L==arr.size())out.push_back(arr);
    f(N,L,arr);
    arr.pop_back();
  }
}

int sum(const vector<int>&arr,const vector<int>&ids){int v=0;for(size_t i=0;i<ids.size();i++)v+=arr[ids[i]];return v;}

bool check(const vector<int>&inp){
  vector<int> e;
  int n=inp.size();
  for(int i=0;i<n;i++)f(n,i+1,e);
  for(int i=0;i<out.size();i++){
    auto&arr=out[i];
    if(0==sum(inp,arr)){for(int i=0;i<arr.size();i++)cout<<inp[arr[i]]<<" ";cout<<endl;return true;}
  }
  return false;
}

int main() {
  int inp_arr[]={2,-7,4,8,1}; int n=5;
  vector<int> inp(inp_arr,inp_arr+n);
  cout<<(check(inp)?"true":"false");
  return 0;
}
#13
5:34, 3 июня 2017

nes
> Девушки на работе проходили какой-то тест, там была задача:

Это что это у вас там за "девушки на работе"? Что это и откуда?

#14
10:04, 3 июня 2017

Panzerschrek[CN]
> Девушки
Это так называют программистов.

Страницы: 1 2 3 4 Следующая »
ФлеймФорумПрограммирование

Тема в архиве.