Форум программистов, компьютерный форум CyberForum.ru

Функция сортировки и поиска - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.93
foruss
1 / 1 / 0
Регистрация: 07.06.2010
Сообщений: 10
07.06.2010, 22:07     Функция сортировки и поиска #1
Ужасная функция...неделю бился так ничего и не смог придумать...Само условие поставленное в задаче звучит так:
"Написать алгоритм, который ищет элементы в массиве следующим образом: Если его длина меньше n, то используется линейный поиск, иначе сортировка слиянием (нерекурсивная), а затем, поиск методом золотого сечения. Эксперементальным путем определить оптимальное значение n для поиска 1000 элементов типов double, int и строк длины 8"
Как написать если меньше n это понятно, в функции делаем цсловие и перебираем. А вот то что должно быть после else....Я уже не понимаю...Помогите кто сможет.
Готов даже $ помочь

Добавлено через 17 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <conio.h>
#include <iostream.h>
#include <math.h>
 
 
//целевая функция
double f(double x)
{
   return exp(x)-2*x;
}
 
 
//поиск минимума методом золотого сечения
double findMinGoldCut(double a,            //левая граница интервала
              double b,            //правая граница интервала
              double sigma,        //погрешность
              double (&f)(double)) //функция
{
   double l = b-a;                                      //длина интервала
   double x1 = a+l*0.3819660113, x2 = a+l*0.6180339887; //пробные точки
   double f_x1 = f(x1), f_x2 = f(x2);                   //значения функции
 
   while(l>sigma)
   {
      if(f_x1<f_x2)
      {
     //исключается правый подынтервал
     l = x2-a; b = x2; x2 = x1; x1 = a+l*.3819660113;
     f_x2 = f_x1; f_x1 = f(x1);
      }
      else
      {
     //исключается левый подынтервал
     l = b-x1; a = x1; x1 = x2; x2 = a+l*.6180339887;
     f_x1 = f_x2; f_x2 = f(x2);
      }
   }
 
   return (b+a)*0.5;
}
 
 
void main()
{
   clrscr();
 
   cout.precision(6);
   cout.setf(ios::fixed|ios::showpoint);
 
   double x = findMinGoldCut(-10,10,.0000001,f);
 
   cout<<"x    = "<<x<<endl;
   cout<<"f(x) = "<<f(x)<<endl;
[OFF][/OFF]
   getch();
}
Вот поиск методом золотого сечения минимума, а нам нужно определенное число только...
И непонятно мне что за цифры там такие...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
foruss
1 / 1 / 0
Регистрация: 07.06.2010
Сообщений: 10
09.06.2010, 20:58  [ТС]     Функция сортировки и поиска #2
Я тут вот помучался...
Кое-что нашел. Может есть знающие люди,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
template <class T>
int gold(T *a, T b, int n, int number_find_element){
  if(!n)
    return -1;
  int m = n - ((pow(5,1/2) + 1) / 2);
  if (a[m] == b)
    return m + number_find_element;
  if (b < a[m])
    return gold(a, b, m, number_find_element);
  else
   return gold(a + m -1, b, n - m - 1, number_find_element + m);
 
}
Вот это поиск золотым сечением? то что выше..
Так...Вот нашел еще код линейного поиска
C++
1
2
3
4
5
6
7
template <class T>
int linfind( T*a, T b,int n){
  for(int i = 0; i < n; i++)
    if(a[i] == b)
      return i;
    return -1;
}
И еще, копался в инете, гуглил, яндексил и везде лазил, так вот нашел Нерекурсивную сортировку слиянием.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// Слияние двух упорядоченных массивов
// m1 - Первый массив
// m2 - Второй массив
// l1 - Длина первого массива
// l2 - Длина второго массива
// Возвращает объединённый массив
template <class T>
T* merge(T *m1, T* m2, int l1, int l2){
    T* ret = new T[l1+l2];
    int n = 0;
    // Сливаем массивы, пока один не закончится
    while (l1 && l2){
        if (*m1 < *m2){
           ret[n] = *m1;
           m1++; l1--;}
        else {
           ret[n] = *m2;
           m2++; l2--;}
       n++;}
    // Если закончился первый массив
    if (l1 == 0){
        for (int i=0; i<l2; i++){
            ret[n++] = *m2++;}}
    // Если закончился второй массив
    else {
        for (int i=0; i<l1; i++){
           ret[n++] = *m1++;}}
    return ret;}
 
// Функция восходящего слияния
template <class T>
void mergeSort(T * mas, int len){
    int n=1, l, ost;
    T * mas1;
    while (n<len){
        l=0;
        while (l<len){
           if (l+n >= len) break;
           ost = (l+n*2>len) ? (len-(l+n)) : n;
           mas1 = merge(mas+l, mas+l+n, n, ost);
           for (int i=0; i<n+ost; i++) mas[l+i] = mas1[i];
           delete [] mas1;
           l+=n*2;}
       n*=2;
}}
Но есть пару проблем. Я не пойму как она работает, что возвращает и как изменяет Короче бред какой то вообще!
И когда я запускал, она не воспринимала массивы типа инт, постоянно ругалась, может я что то недопонимаю? Буду рад если кто мне объяснит и поможет =)
besstiaa
 Аватар для besstiaa
93 / 93 / 7
Регистрация: 04.06.2010
Сообщений: 223
09.06.2010, 22:03     Функция сортировки и поиска #3
Может имеет смысл всё-таки свой код выложить? А то пробовали что-то, что-то не принимает, а тут как сидеть гадать что и как...
foruss
1 / 1 / 0
Регистрация: 07.06.2010
Сообщений: 10
10.06.2010, 08:47  [ТС]     Функция сортировки и поиска #4
Да у меня тоже не работает...еще gcc Напрочь ыбесил. куда то библиотееки пропадают
Yandex
Объявления
10.06.2010, 08:47     Функция сортировки и поиска
Ответ Создать тему
Опции темы

Текущее время: 13:27. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru