12.12.2008, 18:53
|
|
Познающий
Регистрация: 10.11.2006
Сообщений: 57
Провел на форуме:
456672
Репутация:
20
|
|
Задача: найти все перестановки целого числа длинной n. Вот мой алгоритм.
PHP код:
#include <stdio.h>
#include <stdlib.h>
int main()
{
FILE *out;
int data[10]; //10 элементов будет досточно
int n; //кол-во элементов для перестановок
int tmp, min;
int invert;//номер элемента для перестановки
int i, j; //счетчики
int scrambling=0; //кол-во записей
bool go=true;//true-продолжить вычисления, false - остановиться.;
char inbuf[2];
start:
printf("Enter the number(1-9): ");
gets(inbuf);
sscanf(inbuf,"%d",&n); //ввод числа с клавиатуры
if(n<1||n>9) //проверка на введенное число
{
printf("Error!!\n");
goto start;
}
out=fopen("output.txt", "w");
//n=4;
for (i = 0; i < n; i++) //заполняем массив
{
data[i] = i+1;
}
while (go)
{
go = false;
for (i =0; i < n; i++)
{
printf("%d", data[i]); //вывод на экран массива т.е. одной строчки.
fprintf(out, "%d", data[i]);
}
scrambling++;//Количество перестановок увеличилось на единицу.
if(n==1) //если n единица, то выход из цикла.
{
printf("\n");
fprintf(out, "%d", data[i]);
break;
}
/* 1. Двигаемся с предпоследнего элемента перестановки, ищем элемент data[i],
удовлетворяющий неравенству data[i] < data[i + 1] */
for (i = n - 2; i>= 0; i--) //перебираем возможные перестановки
{
if (data[i] < data[i + 1]) //если ни разу не выполяентся, то go останется false,
{
invert=i; //номер элемента, который будем переставлять
go = true;
break;
}
}
if(go==false){break;};
printf("\n");
fprintf(out, "\n");
/* 2. Меняем местами элемент data[invert] с наименьшим элементом, который:
находится праве data[invert] и является больше чем data[invert] */
for (i=invert+1; i<n; i++)
{
if(data[invert]<data[i]){min=i;}
}
tmp=data[invert];
data[invert] = data[min];
data[min] = tmp;
/* 3. Все элементы стоящие правее data[invert] сортируем по возрастанию*/
/*Сортировка пузырьковым методом*/
for (j=invert+1;j<n; j++)
{
for(i=invert+1;i<n-1;i++)
{
if(data[i]>data[i+1])
{
tmp=data[i];
data[i]=data[i+1];
data[i+1]=tmp;
}
}
}
}
printf("\n\nScrambling=%d\n",scrambling);
fclose(out);
system("PAUSE");
return 0;
}
Преподаватель попросил усовершенствовать его, а именно обезопаситься от одинаковых значений (хотя и так понятно, что их там нет), а так же подтворить, что все вариантов перестановок больше нет.
Мои идеи по этому поводу. Перестановок может быть N!, а значит что если N! будет равно scrambling, то перестановок именно нужное кол-во. Препод сказал следующее, а вдруг встретятся одинаковые перестановки, тогда scrambling не будет равно N!.
Что касается одинаковых строчек, можно каждый раз перед выводом(записью) новой строки сравнивать ее со всеми предыдущими из файла, на сколько это угробит скорость работы?
Помогите идеями с этими двумя вопросам. Реализация не обязательно, хотя не откажусь.
Если у вас имеется другие алгоритмы для данной задачи, то хотел бы увидеть их тоже. Тема должна быть близка вам (генераторы паролей, icq номеров и т.п.)
Спасибо за внимание.
Последний раз редактировалось Asp1r1n; 12.12.2008 в 19:13..
|
|
|