Помощь - Поиск - Пользователи - Календарь
Полная версия: Задача > Информатика / Программирование
Образовательный студенческий форум > Другие дисциплины > Информатика / Программирование
ThePoljaL
Даны 3 числа: a, b, c. Определить, можно ли в первых двух числах переставить цифры так, чтобы сумма конечных чисел была равна с. Например а=21; b=31; c=25. Ответ: Можно. 12+13=25
tig81
какой язык?
ThePoljaL
Цитата(tig81 @ 30.10.2011, 11:10) *

какой язык?

Turbo Pascal
граф Монте-Кристо
Можно попробовать перебором.
Sergio Ramos
Как вариант, записать все перестановки каждого числа в отдельный массив и затем по ним пройтись. Если есть ограничение по времени, то укажите, придумаем что-нибудь побыстрее.
ThePoljaL
Цитата(Sergio Ramos @ 31.10.2011, 21:09) *

Как вариант, записать все перестановки каждого числа в отдельный массив и затем по ним пройтись. Если есть ограничение по времени, то укажите, придумаем что-нибудь побыстрее.

ограничение по времени есть. 2 секунды. перебор не подойдет
Sergio Ramos
Цитата(ThePoljaL @ 30.10.2011, 4:08) *

Даны 3 числа: a, b, c. Определить, можно ли в первых двух числах переставить цифры так, чтобы сумма конечных чисел была равна с. Например а=21; b=31; c=25. Ответ: Можно. 12+13=25


Код
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> func(int n,vector<int> a) {
    int k=0;
    bool flag;
while(n/10>0) {
    flag=false;
    for (int i=0;i<a.size();i++)
        if(a[i]==n%10) {
            i=a.size();
            flag=true;
        }
        if (!flag) k++;
        a.push_back(n%10);
    n/=10;
}
for (int i=0;i<a.size();i++)
    if(a[i]==n%10) flag=true;

if(!flag) k++;

a.push_back(n%10);
a.push_back(k);

return a;}

int fact(int n) {
    if (n==0 || n==1) return 1;
    else return n*fact(n-1);
}

int vv (vector<int>a) {
    int n=a[0];
    int des=10;
    for (int i=1;i<a.size();++i) {
        n+=des*a[i];
        des*=10;
    }
    return n;}

int main () {
int num1,num2,result;
cin >> num1 >> num2 >> result;
vector<int> a1;
vector<int> a2;

a1=func(num1,a1);
a2=func(num2,a2);

int k1=fact(a1[a1.size()-1]);
int k2=fact(a2[a2.size()-1]);
a1.erase(a1.end()-1,a1.end());
a2.erase(a2.end()-1,a2.end());

vector<vector<int>> perm1(k1);
vector<vector<int>> perm2(k2);

for (int i=0;i<k1;i++) {
    std::next_permutation(a1.begin(),a1.end());
    perm1[i]=a1;
}

for (int i=0;i<k2;i++) {
    std::next_permutation(a2.begin(),a2.end());
    perm2[i]=a2;
}

bool maker = false;
for (int i=0;i<k1;i++)
for (int j=0;j<k2;j++)
if (vv(perm1[i])+vv(perm2[j])==result) {
    maker = true;
    break;
}

if (maker) cout << "YES";
else cout << "NO";

return 0;}


Делал, как указал выше, получил все перестановки и пытался из них составить 3-е число. Не знаю, на сколько это логично и экономно получилось.
julia_lisha
тема возможно уже неактуальна.
Руководитель проекта
Цитата(julia_lisha @ 15.11.2011, 20:17) *

тема возможно уже неактуальна.

Не нам решать. Мы в обсуждении не участвовали.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.
Русская версия Invision Power Board © 2001-2025 Invision Power Services, Inc.