IPB

Здравствуйте, гость ( Вход | Регистрация )

 
Ответить в эту темуОткрыть новую тему
> Задача, из школьной олимпиады
ThePoljaL
сообщение 30.10.2011, 8:08
Сообщение #1


Новичок
*

Группа: Продвинутые
Сообщений: 3
Регистрация: 30.10.2011
Город: Сергиев Посад
Учебное заведение: Школота
Вы: школьник



Даны 3 числа: a, b, c. Определить, можно ли в первых двух числах переставить цифры так, чтобы сумма конечных чисел была равна с. Например а=21; b=31; c=25. Ответ: Можно. 12+13=25
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
tig81
сообщение 30.10.2011, 8:10
Сообщение #2


Академик
********

Группа: Преподаватели
Сообщений: 15 617
Регистрация: 15.12.2007
Город: Украина, Запорожье
Учебное заведение: ЗНУ
Вы: преподаватель



какой язык?
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
ThePoljaL
сообщение 30.10.2011, 8:13
Сообщение #3


Новичок
*

Группа: Продвинутые
Сообщений: 3
Регистрация: 30.10.2011
Город: Сергиев Посад
Учебное заведение: Школота
Вы: школьник



Цитата(tig81 @ 30.10.2011, 11:10) *

какой язык?

Turbo Pascal
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
граф Монте-Кристо
сообщение 30.10.2011, 14:11
Сообщение #4


Доцент
******

Группа: Преподаватели
Сообщений: 3 840
Регистрация: 27.9.2007
Из: Старый Оскол
Город: Москва
Учебное заведение: МФТИ/МАИ
Вы: другое



Можно попробовать перебором.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Sergio Ramos
сообщение 31.10.2011, 18:09
Сообщение #5


Студент
**

Группа: Продвинутые
Сообщений: 86
Регистрация: 16.11.2010
Город: Saratov



Как вариант, записать все перестановки каждого числа в отдельный массив и затем по ним пройтись. Если есть ограничение по времени, то укажите, придумаем что-нибудь побыстрее.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
ThePoljaL
сообщение 3.11.2011, 16:20
Сообщение #6


Новичок
*

Группа: Продвинутые
Сообщений: 3
Регистрация: 30.10.2011
Город: Сергиев Посад
Учебное заведение: Школота
Вы: школьник



Цитата(Sergio Ramos @ 31.10.2011, 21:09) *

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

ограничение по времени есть. 2 секунды. перебор не подойдет
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Sergio Ramos
сообщение 15.11.2011, 14:55
Сообщение #7


Студент
**

Группа: Продвинутые
Сообщений: 86
Регистрация: 16.11.2010
Город: Saratov



Цитата(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
сообщение 15.11.2011, 16:17
Сообщение #8


Студент
**

Группа: Продвинутые
Сообщений: 147
Регистрация: 19.12.2009
Из: Omsk
Город: omsk
Учебное заведение: ОмГУ



тема возможно уже неактуальна.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Руководитель проекта
сообщение 15.11.2011, 17:29
Сообщение #9


Руководитель проекта
******

Группа: Руководители
Сообщений: 3 189
Регистрация: 23.2.2007
Из: Казань
Город: Казань
Учебное заведение: КГУ
Вы: другое



Цитата(julia_lisha @ 15.11.2011, 20:17) *

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

Не нам решать. Мы в обсуждении не участвовали.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения

Ответить в эту темуОткрыть новую тему
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия Сейчас: 25.5.2025, 15:57

Книжки в помощь: "Сборник заданий по высшей математике" Кузнецов Л.А., "Сборник заданий по высшей математике" Чудесенко В.Ф., "Индивидуальные задания по высшей математике" Рябушко А.П., и другие.




Зеркало сайта Решебник.Ру - reshebnik.org.ru