алгоритм выбора делением списка почти
/* алгоритм выбора делением списка почти пополам */ int search (int *b, int n, int i) { int findi(int *, int, int); int t, m, j, p, s, *w; if (n=m) j++; if (j>i) { for (p=0, t=0; p < n; t++) if (b[t]>=m) { b[p]=b[t]; p++; } m=search(b, j, i); /* поиск в B" */ } if (j < i) { for (p=0, t=0; t < n; t++) if (b[t] < m) b[p++]=b[t]; m=search(b, n-j, i-j); /* поиск в B" */ } return m; }
Рекурсивная функция search реализует алгоритм выбора i-того наибольшего значения. Для ее вызова можно использовать следующую программу
#include
#include
main() { int search (int *b, int n, int i); int *b; int l, i, k, t; scanf("%d%d",&l,&i); printf ("\nВыбор %d максимального элемента из %d штук",i,l); b=(int *)(calloc(100,sizeof(int))); for (k=0; k
Используя метод математической индукции, можно доказать, что для функции search требуется выполнить в самом неблагоприятном случае 28*N сравнений.
Действительно, если N<21, то выполнение функции findi потребует сравнений порядка N*(N-1)/2, т.е. меньше чем 28*N. Предположим, что для любого T<N количество сравнений при выполнении функции search не более 28*T и подсчитаем, сколько сравнений потребуется функции search при произвольном значении N. Для поиска медианы в каждом из подсписков функцией findi требуется не более 7*(7-1)/2=21 сравнений, а для формирования массива W в целом не более 21*(N/7)=3*N сравнений. По предположению индукции для поиска медианы в массиве W длины N/7 требуется 28*(N/7)=4*N сравнений. После удаления из B части элементов с помощью медианы в B' (или в B") останется не более N*5/7 элементов, и для удаления ненужных элементов необходимо количество сравнений порядка N. Для поиска в оставшейся части массива (в B' или B") по предположению индукции требуется не более 28*(N*5/7)=20*N сравнений. Таким образом, всего потребуется 3*N+4*N+N+20*N=28*N сравнений, т.е. выдвинутое предположение доказано.
[ | | ]
Copyright ©
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий