дано N кубиков, на кубике уникальное число, упорядочить за минимальное количество обменов. Откровенно говоря теряюсь в догадках собственно процесса вот этого поиска минимального количества обменов.... Потому очень прошу помочь написанием этой проги на Си, особо благодарен буду если в исходник внедрите хоть небольших комментарии процесса, дабы понять происходящее.....
-Lord-
20.11.2006 17:59
Хотелось бы отметить, что если к тонить знает верное решение, но в написании программы затрудняется, то скажите хоть ход мыслей.... но вообще конечно оооочень прошу помочь и исходничком
klem4
20.11.2006 20:56
Если все элементы уникальны (нет повторяющихся) то вот мне видится, что минимального количества перестановок можно достичь так:
# include <stdio.h> # include <stdlib.h> # include <conio.h>
int main(void) { clrscr(); // очистка экрана
int *cube, n; // 2 переменные массив и размерность массива
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]); // выводим массив
понятно спасибо. Если найдёшь время добавь пожалуйста комментарии уж очень детально понять хочется... а знаний немного нехватает
klem4
20.11.2006 23:44
Добавил комменты ...
Гость
4.12.2006 21:58
Здравствуйте. Огромное спосибо за решение. Во твозник вопрос решение которого немног озбивает с толку, а каким образом можно доказать что получается реально минимальное количество перестановок. Нам сказали что есть некий способ доказать от противного (не обязательно так но можно), но вот излишних подробностей не сообщили - вот очень прошу помочь, а галвнео понять яки это делается
Гость
5.12.2006 4:43
Прошу помочь разобраться, а то даже не знаю с каког оконца подойти
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.