вы должны делать:
асть назначения основана на массиве (его размер задается пользователем), который содержит случайные числа от 1 до 10 ^ 10. Затем мы должны найти k-й меньший номер массива. Вот что я попробовал:
#include <cstdlib>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <time.h>
using namespace std;
void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
int choose_pivot(int i,int j )
{
return((i+j) /2);
}
// Print array
void printarr(int arr[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d\t",arr[i]);
}
// Find algorithm
int find1(int arr[],int left,int right,int k)
{
int i,j,pivot;
if (left==right)
return arr[left];
else
{
i=left;
j=right+1;
pivot= arr[left];
do
{
do {
i=i+1;
} while (arr[i]>=pivot);
do {
j =j-1;
} while (arr[j]<=pivot);
if (i<j)
swap(arr[i],arr[j]);
} while (j<=i);
}
swap(arr[left],arr[j]);
if (k==j)
return arr[j];
else if (k<j)
find1(arr,left,j-1,k);
else
find1(arr,j+1,right,k-j);
}
int main(int argc, char *argv[])
{
srand(time(NULL));
int n,i,fi,k;
printf("Give array's size:\n");
scanf("%d",&n);
int pin[n];
for (i=0;i<n;i++)
pin[i]=((rand()*rand()) % 1000000000) +1;
printf("Give k: \n");
scanf("%d",&k);
printf("The array contains the following numbers:\n\n");
printarr(pin,n);
fi=find1(pin,0,n-1,k);//find the k-th smallest number in the array
printf("The k-th smallest number is: %d",fi);
system("PAUSE");
}
Как видите, 10 ^ 10 - это очень большое значение, и я сделал что-то еще, чтобы заполнить массив случайными числами. Это правильно? Есть ли что-то еще, что я мог сделать? И моя вторая проблема - алгоритм поиска. Не работает Может ли кто-нибудь помочь мне с этим? большое спасибо