IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным. В описании темы указываем язык!!!

 
 Ответить  Открыть новую тему 
> поиск минимальной суммы произведений, Чистый С
сообщение
Сообщение #1


Гость






Доброго времени суток.
Поставили перед мною следующую задачу и наказили выполнить на С.
Данны 2 массива длины n. Можно брать по одному члену из каждого м перемножать их. Напистаь программу печатающую пары номеров массивов так, чтобы сумма их произведений была минимальной. Каждый член массива может использоваться лишь однажды.

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

Благодарю за внимание.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Условие такое. Даны два набора чисел, по n в каждом. К примеру:

1) 2 5 1
2) 3 3 1

Мы можем расположить числа в произвольном порядке, например:

1) 1 2 5
2) 3 3 1

или

1) 5 2 1
2) 3 1 3

Выбрав некоторое расположение, мы умножаем числа попарно, и складываем результаты. Например:


1) 5 1 2
2) 1 3 3

5*1 + 1*3 + 2*3 = 14

Нужно расположить числа так, чтобы полученное произведение оказалось максимально возможным.

Решение: нужно просто отсортировать оба массива. В нашем случае:

1) 1 2 5
2) 1 3 3

1*1 + 2*3 + 5*3 = 22

Чтобы доказать, что это правильно, покажем, что, сортируя, мы улучшаем результат. Пусть на некотором месте в верхней строке стоит число А, в нижней строке - а, а на другом месте, в верхней строке стоит В, в нижней - в. Имеем: Aa+Bb. Легко убедиться, что множить наоборот, т.е. Ab+Ba, будет выгоднее только тогда, когда порядок чисел A,B и a,b - разный, т.е. когда (A-B)(a-b)<0 - это получается непосредственно из предположения, что Ab+Ba>Aa+Bb. Применяя это рассуждение много раз, получим что-то вроде пузырьковой сортировки smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






Огромное спасибо я вот написал что то вроди этого, но возникала пробелма -как мне вывести индексы - мне на выход нужно передать индексы этих пар в старом массиве - не отсортированном. Т.е. я должен не только отсортировать массив но ещё и хранить индекс каждого элемента в массиве до его сортировки, чтобы на выходе можно было увидеть что мол элемент 2 * элемент 4 + элемент 6 * 7 элэмент....
Вот прошу помочь


#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

#define MAX 3
#define OBNUL 0

main ()
{
int i;
int mas1[MAX] = {12,2,4}; // массив 1
int mas2[MAX] = {8,42,34}; // массив 2
int m1_t[MAX];
int m2_t[MAX];
int obn, nbl; // переменная счётчик
int min, max, vrem;
obn = OBNUL; nbl = OBNUL; min = OBNUL; max = OBNUL; vrem = OBNUL;
min = mas1[1];

for(obn = OBNUL, i=0; obn < MAX; obn++, i++)
{
min = mas1[obn];
for (nbl = OBNUL; nbl < MAX; nbl++)
{
if (mas1[nbl] > min)
{
m1_t[i] = obn;
vrem = mas1[nbl];
mas1[nbl] = min;
mas1[obn] = vrem;
break;
}
}
}


for(obn = OBNUL; obn < MAX; obn++)
{
for (nbl = OBNUL; nbl < MAX; nbl++)
{
if (mas2[nbl] < mas2[obn])
{
vrem = mas2[nbl];
mas2[nbl] = mas2[obn];
mas2[obn] = vrem;
break;
}
}
}
for(obn = OBNUL; obn < MAX; obn++)
printf("%d\n", mas1[obn]);
printf("----------\n");
for(obn = OBNUL; obn < MAX; obn++)
printf("%d\n", mas2[obn]);
printf("----------\n");


 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Цитата
я должен не только отсортировать массив но ещё и хранить индекс каждого элемента в массиве до его сортировки

#include <stdio.h>

#define MAX 3
#define OBNUL 0

void swap(int *a, int *b) {
int T;
T = *a; *a = *b; *b = T;
}

main ()
{
int i, j;
int mas1[MAX] = {12,2,4};
int mas2[MAX] = {8,42,34};

int ix_1[MAX] = {1, 2, 3},
ix_2[MAX] = {1, 2, 3};

int obn = OBNUL;

for(i = 0; i < MAX; ++i)
for(j = MAX - 1; j >= i + 1; --j) {
if(mas1[j - 1] > mas1[j]) {
swap(&mas1[j - 1], &mas1[j]);
swap(&ix_1[j - 1], &ix_1[j]);
}

if(mas2[j - 1] > mas2[j]) {
swap(&mas2[j - 1], &mas2[j]);
swap(&ix_2[j - 1], &ix_2[j]);
}
}

for(obn = OBNUL; obn < MAX; obn++)
printf("%d(%d) ", mas1[obn], ix_1[obn]);
printf("\n----------\n");
for(obn = OBNUL; obn < MAX; obn++)
printf("%d(%d) ", mas2[obn], ix_1[obn]);
printf("\n----------\n");

return 0;

}
Идея понятна?
 К началу страницы 
+ Ответить 

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

 




- Текстовая версия 20.11.2017 20:18
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"