Перестановки, на Си Опции

[-Lord-]

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

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

[-Lord-]

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

[klem4]

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

# 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;
}

[Гость]

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

[klem4]

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

[Гость]

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

[Гость]

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