Задача: Исследование алгоритмов линейного и двоичного поиска, оптималь

Тема в разделе "C/C++/C#", создана пользователем Best, 7 дек 2010.

Статус темы:
Закрыта.
  1. Best

    Best Гость

    1. Написать программы работы алгоритмов оптимального и неоптимального, последовательного поиска для неупорядоченного массива с оценкой временных характеристик
    2. Написать программы работы алгоритмов последовательного оптимального и бинарного (оптимального и неоптимального) поиска в упорядоченном массиве с оценкой временных характеристик.
    3. Для проведения исследований временных характеристик написать программу формирования одномерного массива, содержащего заданное количество различных элементов целого типа.

    Всё это должно быть в одной проге. Заранее спасибо.
     
  2. DarkKnight

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Свои наработки какие-нибудь есть???
     
  3. Best

    Best Гость

    Нет(((
     
  4. DarkKnight

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Это конечно плохо... И не приветствуется... Но я посмотрю завтра ваши задачи
     
  5. Best

    Best Гость

    Спасибо большое я просто новичёк еще.
     
  6. DarkKnight

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    А какие имеено алгоритмы поиска использовать, я про именно оптималые говорю... потому как с неоптимальными мне все понятно (линейный метод последовательного перебора, и бинарный, а вот с проверкой на оптимальность и много всяких, какой был рассмотрен в лекции....
     
  7. Best

    Best Гость

    Вот этого я незнаю к сожалению...
     
  8. DarkKnight

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Вот:
    Код (C++):
    /*
    codeby.net
    Autor: DarkKnight125 (Denis Goncharov)
    */

    #include <iostream>
    #include <time.h>

    using namespace std;

    //Функция для переставления местами переменных (для сортировки использовал)
    void SwapVal (int &a, int &b)
    {
    int Temp = a;
    a = b;
    b = Temp;
    }
    //Основная функция программы (точка входа)
    void main(void)
    {
    setlocale(LC_ALL,".1251"); //Подгрузка локали
    srand(NULL); //Инициализация таймера случ. величины

    int Arr[100000]; //Массив на 100,000 элементов

    int lIndex = -1; //Индекс элемента (требуемого найти)
    int SerchElem; //Его значение

    //Генерация массива
    cout << "Генерация массива случ. величинами ..." << endl;
    for(int i = 0; i < 100000; i++)
    {
    Arr[i] = rand()%1000000 * (rand()%2?1:-1);
    }
    cout<< "Сгенерирован массив из 100,000 элементов в диапозоне [-999999, 999999]" <<endl;
    cout<< "Введите элемент для поиска : ";
    cin >> SerchElem;

    time_t pStart = clock(); //Сделаем засечку
    //Линейный поиск (методом перебора)
    for (int i = 0; i< 100000; i++)
    if (Arr[i] == SerchElem)
    lIndex = i;

    if (lIndex > -1)
    cout << "Элемент найден, позиция элемента = " << lIndex << endl;
    else cout << "Элемент не найден" << endl;
    cout << "Время поиска линейным перебором : "<< (double)(clock()-pStart)/1000 << " мсек"<< endl;

    //Отсортировать массив по возрастанию (методом улучшенного пузырька)
    cout<< endl << "Выполняется сортировка ..." << endl;
    pStart = clock(); //Сделаем временную засечку для сортировки
    bool MustSort = true;
    for (int i = 0; i < 100000 && MustSort; i++)
    {
    MustSort = false;
    for (int j = 0; j < 100000 - 1 - i; j++)
    if (Arr[j] > Arr[j+1])
    {
    SwapVal(Arr[j],Arr[j+1]);
    MustSort = true;
    }
    }
    cout << "Сортировка выполнена, время выполнения : "<< (double)(clock()-pStart)/1000 << " мсек" << endl;

    //Поиск Дроичный (Бинарный)
    cout << endl << "Выполнение двоичного(бинарного) поиска ..." << endl;
    pStart = clock(); //Сделаем временную засечку
    int bFirst = 0; //Начальный индекс массива (отсортированного)
    int bEnd = 100000 - 1; //Конечный индекс массива (отсортированного)
    int bMiddle; //Переменная середины массива
    lIndex = -1;
    if (SerchElem < Arr[bFirst] || SerchElem > Arr[bEnd])
    cout << "Элемент поиска лежит вне массива" << endl;
    while ( bFirst < bEnd) //Пока вычисляемые индексы Начала меньше выч. индекса Конца
    {
    bMiddle = (bFirst + bEnd) / 2; //Найдем индекс середины
    if (SerchElem <= Arr[bMiddle]) //Если элемент поиска <= значение массива при срединном индексе
    bEnd = bMiddle; //Сместим тогда конец в середину, ведь наш элемент лежит от нач. до средины, или же в аккурат середины
    else //Иначе лежит в пределеот (средина, конец]
    bFirst = bMiddle + 1;
    }
    if (Arr[bEnd] == SerchElem) //Если индекс конца указывает на эл. поиска
    cout << "Элемент найден, позиция элемента = " << bEnd << endl;
    else cout << "Элемент не найден" << endl;   
    cout << "Время поиска двоичным перебором : "<< (double)(clock()-pStart)/1000 << " мсек"<< endl;
    }
    Когда найдешь оптимальные методы напиши, подкорректирую... Но думаю это не получиться....
    Оптимальность - это характеристика функции, а у тебя по примеру рандомный массив..
    Так что оба метода (алгоритма) - являются как оптимальными, так и не оптимальными одновременно... (это я про рандомность говорю)
    уже в отсортированном массиве можно подумать про оптимальность (но момент с двоичным поиском все же в тоже время опять же является как оптимальным так и не оптимальным, иными словами - однозначен)
     

    Вложения:

    • algserch.jpg
      algserch.jpg
      Размер файла:
      59 КБ
      Просмотров:
      23
  9. Best

    Best Гость

    Спасибо большое!!!
     
Загрузка...
Похожие Темы - Задача Исследование алгоритмов
  1. Янчик
    Ответов:
    0
    Просмотров:
    489
  2. TrishaRay
    Ответов:
    1
    Просмотров:
    783
  3. elzim
    Ответов:
    0
    Просмотров:
    932
  4. ShaoKahn
    Ответов:
    1
    Просмотров:
    1.125
  5. eremin-sanek
    Ответов:
    3
    Просмотров:
    1.107
Статус темы:
Закрыта.

Поделиться этой страницей