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

> Внимание!

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

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> Перестановки, на Си
сообщение
Сообщение #1


Гость






Вечре добрый.
Вот получил такую задачу.

дано N кубиков, на кубике уникальное число, упорядочить за минимальное количество обменов.
Откровенно говоря теряюсь в догадках собственно процесса вот этого поиска минимального количества обменов.... Потому очень прошу помочь написанием этой проги на Си, особо благодарен буду если в исходник внедрите хоть небольших комментарии процесса, дабы понять происходящее.....
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Хотелось бы отметить, что если к тонить знает верное решение, но в написании программы затрудняется, то скажите хоть ход мыслей.... но вообще конечно оооочень прошу помочь и исходничком
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

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


Если все элементы уникальны (нет повторяющихся) то вот мне видится, что минимального количества перестановок можно достичь так:

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

int main(void)
{
clrscr(); // очистка экрана

int *cube, n; // 2 переменные массив и размерность массива

printf("n = "); scanf("%d", &n); // читаем размерность массива

cube = (int*)malloc(n * sizeof(int)); // выделяем память под массив (см. malloc в хелпе ...)

for (unsigned i = 0; i < n; i++) // цикл: заполняем массив
{
printf("cube[%d] = ", i);
scanf("%d", (cube + i));
}

int PCOUNT = 0; // обнуляем счетчик перестановок

for (i = 0; i < n - 1 ; i++) // для каждого элемента от первого до _предпоследнего_ ....
{
int nPos = i; // его новая позиция в массиве пока прежная

for (int j = i; j < n; j++) // просматриваем все элементы которые следуют за ним
if ((cube[j] < cube[nPos])) /* если какой-то из них < исследуемого, значит, исследуемый элемент не на своей позиции, меняем ее */
nPos = j;

if (nPos != i) // если для элемента была найдена новая позиция, меняем местами ...
{
int T = cube[i];
cube[i] = cube[nPos];
cube[nPos] = T;

PCOUNT++; // и увеличиваем счетчик перестановок
}

}

printf("\n");

for (i = 0; i < n; i++)
printf("%3d", cube[i]); // выводим массив

printf("\nswaps = %d", PCOUNT); // выводим вол-во перестановок

getche();

return 0;
}



--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






понятно спасибо.
Если найдёшь время добавь пожалуйста комментарии уж очень детально понять хочется... а знаний немного нехватает
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

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


Добавил комменты ...


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






Здравствуйте.
Огромное спосибо за решение.
Во твозник вопрос решение которого немног озбивает с толку, а каким образом можно доказать что получается реально минимальное количество перестановок.
Нам сказали что есть некий способ доказать от противного (не обязательно так но можно), но вот излишних подробностей не сообщили - вот очень прошу помочь, а галвнео понять яки это делается
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






Прошу помочь разобраться, а то даже не знаю с каког оконца подойти
 К началу страницы 
+ Ответить 

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

 





- Текстовая версия 23.09.2020 16:58
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name