Главная страница
Навигация по странице:

  • 2. Внутренняя сортировка данных методом выбора. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

  • 3. Внутренняя сортировка данных методом простых вставок. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

  • 4. Внутренняя сортировка данных методом Шелла. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

  • 5. Внутренняя сортировка данных методом «пузырька». Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

  • 6. Внутренняя сортировка данных «быстрым» методом. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

  • 7. Численное решение уравнения методом половинного деления (дихотомии). Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

  • 8. Численное решение уравнения методом хорд. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

  • 9. Численное решение уравнения методом Ньютона (касательных). Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

  • 11. Численное решение уравнения методом секущих. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

  • 12. Численное решение уравнения методом простых итераций. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

  • 13. Численное интегрирование методом прямоугольников. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Метод прямоугольников

  • Пример для левых прямоугольников

  • Пример для средних прямоугольников

  • Пример для правых прямоугольников

  • 14. Численное интегрирование методом трапеций. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Метод трапеций

  • 15. Численное интегрирование методом парабол. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

  • 1. Внутренняя сортировка данных методом подсчета. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм


    Скачать 103.69 Kb.
    Название1. Внутренняя сортировка данных методом подсчета. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм
    АнкорVoprosy_1-23.docx
    Дата16.08.2018
    Размер103.69 Kb.
    Формат файлаdocx
    Имя файлаVoprosy_1-23.docx
    ТипДокументы
    #21735


    1. Внутренняя сортировка данных методом подсчета. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

    Сортировка подсчётом — алгоритм сортировки массива, при котором подсчитывается число одинаковых элементов. Алгоритм выгодно применять, когда в массиве много элементов, но все они достаточно малы.

    Идея сортировки указана в названии — нужно подсчитывать число элементов, а затем выстраивать массив. Пусть, к примеру, имеется массив A из миллиона натуральных чисел, меньших 100. Тогда можно создать вспомогательный массив B из 99 (1..99) элементов, «пробежать» весь исходный массив и вычислять частоту встречаемости каждого элемента — то есть если A[i]=a, то B[a] следует увеличить на единицу. Затем «пробежать» счетчиком i массив B, записывая в массив A число i B[i] раз.

    void CountingSort (int *a, int n, int min, int max)

    {

    int i, j, c, *b;

    for (i = 0; i for (j = min; j 0)

    {

    *a = j;

    ++a;

    --c;

    }

    }

    }

    2. Внутренняя сортировка данных методом выбора. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

    Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке. Если входная последовательность почти упорядочена, то сравнений будет столько же, значит алгоритм ведет себя неестественно.

    Наихудший случай:

    Число сравнений в теле цикла: (N-1)*N/2.

    Число сравнений в заголовках циклов: (N-1)*N/2.

    Число сравнений перед операцией обмена: N-1.

    Суммарное число сравнений: N2-1.

    Число обменов: N-1.

    void selectSort(int* arr, int size)

    {

    int tmp, i, j, pos;

    for(i = 0; i < size; ++i) // i - номер текущего шага

    {

    pos = i;

    tmp = arr[i];

    for(j = i + 1; j < size; ++j) // цикл выбора наименьшего элемента

    {

    if (arr[j] < tmp)

    {

    pos = j;

    tmp = arr[j];

    }

    }

    arr[pos] = arr[i];

    arr[i] = tmp; // меняем местами наименьший с a[i]

    }

    }

    3. Внутренняя сортировка данных методом простых вставок. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

    На каждом шаге алгоритма, мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор пока набор входных данных не будет исчерпан. Выбор очередного элемента, выбираемого из исходного массива — произволен, может использоваться практически любой алгоритм выбора.

    эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;

    эффективен на наборах данных, которые уже частично отсортированы;

    это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);

    может сортировать список по мере его получения;

    void insertSort(array_type a[], int length)

    {

    int i, j;

    for (i = 1; i < length; i++) { value = a[i]; for (j = i-1; (j >= 0) && (a[j] > value); j--) {

    a[j+1] = a[j];

    }

    a[j+1] = value;

    }

    }

    4. Внутренняя сортировка данных методом Шелла. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

    Алгоритм состоит в том, что исходная последовательность разделяется на ряд групп, каждая из которых упорядочивается методом простой вставки. В процессе упорядочивания размеры групп возрастают до тех пор, пока все элементы не войдут в упорядоченную группу. Группой называется подмножество элементов последовательности, номера которых образуют арифметическую прогрессию с разностью d (d называется шагом группы).

    void sort_Shell(int *mas,int n)

    {

    int i,j; //"бегунки"

    int temp; //вспомогательная переменна

    int h = n/2;

    while(h>0)// проверяем, если h>0 то входим в тело цикла

    {

    for(i=0;i mas[j+h])

    {

    temp = mas[j];

    mas[j] = mas[j+h];

    mas[j+h] = temp; //перестановка элементов

    j=j-h;

    }

    else

    j=-1;// перестановки не было - "бегунок" уменьшим на 1

    }

    }

    h=h/2;

    }

    }

    5. Внутренняя сортировка данных методом «пузырька». Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

    Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.

    Наихудший случай:

    Число сравнений в теле цикла равно: (N-1)*N/2.

    Число сравнений в заголовках циклов равно: (N-1)*N/2.

    Суммарное число сравнений равно: (N-1)*N.

    Число присваиваний в заголовках циклов равно: (N-1)*N/2.

    Число обменов равно: (N-1)*N/2, что в N/2 раз больше, чем в сортировке выбором.

    void bubbleSort(int* arr, int size)

    {

    int tmp, i, j;
    for(i = 0; i < size - 1; ++i) // i - номер прохода

    {

    for(j = 0; j < size - 1; ++j) // внутренний цикл прохода

    {

    if (arr[j + 1] < arr[j])

    {

    tmp = arr[j + 1];

    arr[j + 1] = arr[j];

    arr[j] = tmp;

    }

    }

    }

    }

    6. Внутренняя сортировка данных «быстрым» методом. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

    Идея:

    - выбрать элемент, называемый опорным.

    - сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.

    - повторить рекурсивно для «меньших» и «больших».

    Количество обменов в худшем случае: n^2

    Количество шагов деления(глубина рекурсии):

    log n

    void qSort(int[] A, int low, int high) {

    int i = low;

    int j = high;

    int x = A[(low+high)/2];

    do {

    while(A[i] < x) ++i;

    while(A[j] > x) --j;

    if(i int temp = A[i];

    A[i] = A[j];

    A[j] = temp;

    i++; j--;

    }

    } while(i
    if(low < j) qSort(A, low, j);

    if(i < high) qSort(A, i, high);

    }

    7. Численное решение уравнения методом половинного деления (дихотомии). Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

    Метод дихотомии заключается в последовательном делении отрезка. Выберется промежуток функции, при этом, отделив корни, например, графическим способом. Получив интервал функции вычисляется его середина и определяется какой отрезок функции, разделенный серединой, больше или меньше нуля, это необходимо для выбора дальнейшего сужения интервала. Процесс сужения продолжается до определенной погрешности, которая задается пользователем.

    К плюсам данного метода, конечно, стоит отнести его простоту. Им легко вычислять как аналитически, так и программно. К минусам нужно отнести затраты на приведенные итерации, по сравнению с методом хорд и касательных, например.

    Алгоритм данного метода можно записать так:

    1. Ввести данные (a, b, ε).

    2. Если нужная точность достигнута (|b-a|<2ε) то идти к п.6

    3. Взять середину очередного отрезка (c=(a+b)/2).

    4. Если значения функции в точках а и c одного знака (f(a)*f(с)>0), то в качестве следующего отрезка взять правую половину (а=c), иначе — левую (b=c).

    5. Идти к п.2.

    6. Напечатать ответ ((a+b)/2)

    double l=a, r=b; // границы отрезка

    const double EPS = 1E-9; // точность

    while (r-l > EPS) {

    double m = (l + r) / 2;

    if (f (m)*f (r) > 0)

    r = m;

    else

    l = m;

    }

    8. Численное решение уравнения методом хорд. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

    Идея метода хорд состоит в том, что можно с известным приближением допустить, что функция на достаточно малом участке [а, b] изменяется линейно. Тогда кривую у = f(х) на участке [а, b] можно заменить хордой и в качестве приближенного значения корня принять точку пересечения хорды с осью абсцисс.

    Для применения метода функция у = f(х) должна обладать следующими свойствами:

    1. Быть непрерывной на [а, b] и f(a)f(b)<0.

    2. На [а, b] существуют f/(x) и f//(x) отличные от нуля, непрерывные и сохраняющие знак на данном отрезке.

    double func(double x)

    {

    return pow(x, 3) - 2 * pow(x, 2) - 6 * x - 1;

    }

    double find(double infinum, double supremum, double epsilon)

    {

    while (fabs(supremum - infinum) > epsilon)

    {

    infinum = supremum - (supremum - infinum) * func(supremum) / (func(supremum) - func(infinum));

    supremum = infinum - (infinum - supremum) * func(infinum) / (func(infinum) - func(supremum));

    }

    return supremum;

    }

    int main()

    {

    double a = -5, b = 5;

    std::cout << find(a, b, 0.0001) << std::endl;

    return 0;

    }

    9. Численное решение уравнения методом Ньютона (касательных). Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

    Этот метод применяется только в том случае, когда f’(x) и f(x) не изменяют знака на отрезке [a,b], т.е. функция f(x) на отрезке [a,b] монотонна и не имеет точек перегиба.

    Суть метода — построение последовательности вложенных отрезков, содержащих корень, однако отрезки строятся по-другому. На каждом шаге через концы дуги графика функции f(x) на очередном отрезке проводят хорду и из одного конца проводят касательную. Точки пересечения этих прямых с осью ОХ и образуют следующий отрезок.

    Для того, чтобы отрезки получались вложенными, нужно проводить ту касательную из конца, которая пересекает ось ОХ на отрезке [a,b]. Перебрав четыре возможных случая (разные знаки f’(x) и f(x)), можно увидеть, что касательную следует проводить из того конца, где знак функции совпадает со знаком второй производной. Также можно заметить, что касательная проводится либо все время из правого, либо все время из левого конца. Будем считать для определенности, что этот конец — b.

    const double a = 0.0;

    const double b = 1.0;

    const double x0 = 0.5;

    const double epsilon = 0.000001;

    double f(double x)

    {

    return (x-0.25)*(x-0.25);

    }

    double df(double x)

    {

    return 2*x;

    }

    int main(int argc , char *argv[])

    {

    double x = x0;

    while (abs(f(x)) > epsilon) {

    x = x - f(x)/df(x);

    }

    std::cout << x << std::endl;

    }

    11. Численное решение уравнения методом секущих. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

    Алгоритм вроде такой же, как и в методе Ньютона, только сравниваем не так:

    while (abs(f(x)) > epsilon)

    А так:

    while (abs(f(x)) < epsilon)


    const double a = 0.0;

    const double b = 1.0;

    const double x0 = 0.5;

    const double epsilon = 0.000001;

    double f(double x)

    {

    return (x-0.25)*(x-0.25);

    }

    double df(double x)

    {

    return 2*x;

    }

    int main(int argc , char *argv[])

    {

    double x = x0;

    while (abs(f(x)) < epsilon)

    {

    x = x - f(x)/df(x);

    }

    std::cout << x << std::endl;

    }

    12. Численное решение уравнения методом простых итераций. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

    Применяется к уравнению вида x=u(x) на отрезке [a,b], где:

    1. модуль производной функции u(x) невелик: |u’(x)|<=q<1 (x∈[a,b])

    2. значения u(x) лежат на [a,b], т.е. a<=u(x)<=b при x∈[a,b].

    Но так как мы точно знаем (из первого этапа решения задачи), что на этом отрезке есть корень, и он только один, то условие 2 можно опустить.

    Сведение уравнения f(x)=0 к нужному виду обычно осуществляют так: выражают один из x, входящих в уравнение, например уравнение е^х-х-7=0 приводят к виду: x=е^x-7 или x=ln(x+7).

    В первом случае |u’(x)|=|e^x| на левом конце отрезка (0) не меньше единицы, что не подходит по условию 1, во втором же случае |u’(x)|=|1/(x+7)| явно меньше единицы, что нас и устраивает.

    Суть метода итераций заключается в построении рекуррентной последовательности чисел, сходящейся к решению, по формуле хк+1 = u(xк), к=0,1,2,…, где х0∈[a,b] -произвольная точка. Для удобства можно вводить х0=a.

    #define TESTPRINT
    double Equation( double x ) {

    return pow( cos(x+0.5), (double)(1./3.) );

    }

    int main() {

    const double eps = 0.0001;

    double x0, x, xNext;

    int nIter;

    printf( "x0 = ? " ); scanf( "%lg", &x0 );

    x = x0;

    xNext = Equation( x );

    nIter = 1;

    while ( fabs( xNext-x ) > eps ) {

    x = xNext;

    xNext = Equation( x );

    ++nIter;

    #ifdef TESTPRINT

    printf( "%.5g %.5g %d\n", x, xNext, nIter );

    #endif

    }

    printf( "The root %.5g has been reached to within %.5g after %d iterations.\n",

    xNext, eps, nIter );

    getch();

    return 0;

    }

    13. Численное интегрирование методом прямоугольников. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

    Метод прямоугольников — метод численного интегрирования функции одной переменной, заключающийся в замене подынтегральной функции на многочлен нулевой степени, то есть константу, на каждом элементарном отрезке. Если рассмотреть график подынтегральной функции, то метод будет заключаться в приближённом вычислении площади под графиком суммированием площадей конечного числа прямоугольников, ширина которых будет определяться расстоянием между соответствующими соседними узлами интегрирования, а высота — значением подынтегральной функции в этих узлах.

    http://upload.wikimedia.org/wikipedia/commons/4/4a/leftriemann.png

    Левые прямоугольники

    http://upload.wikimedia.org/wikipedia/commons/8/8e/midriemann.png

    Средние прямоугольники

    http://upload.wikimedia.org/wikipedia/commons/4/49/rightriemann.png

    Правые прямоугольники

     

    Пример для левых прямоугольников:

    double f(double x){

    return sin(x);

    }
    double rectangle_integrate(double a, double b, int n, double (*f)(double) ){

    double result, h;

    int i;
    h = (b-a)/n;

    result = 0.0;
    for(i=0; i result += f( a + h * i );

    }

    result *= h;
    return result;

    }
    int main(void){

    double integral;

    integral=rectangle_integrate(0,2,100,f);

    printf("The value of the integral is: %lf \n", integral);

    }

    Пример для средних прямоугольников:

    double f(double x){

    return sin(x);

    }
    double rectangle_integrate(double a, double b, int n, double (*f)(double) ){

    double result, h;

    int i;
    h = (b-a)/n;

    result = 0.0;
    for(i=1; i result += f( a + h * (i - 0.5) );

    }

    result *= h;
    return result;

    }
    int main(void){

    double integral;

    integral=rectangle_integrate(0,2,100,f);

    printf("The value of the integral is: %lf \n", integral);

    }

    Пример для правых прямоугольников:

    double f(double x){

    return sin(x);

    }
    double rectangle_integrate(double a, double b, int n, double (*f)(double) ){

    double result, h;

    int i;
    h = (b-a)/n;

    result = 0.0;
    for(i=1; i result += f( a + h * i );

    result *= h;
    return result;

    }
    int main(void){

    double integral;

    integral=rectangle_integrate(0,2,100,f);

    printf("The value of the integral is: %lf \n", integral);

    }

    14. Численное интегрирование методом трапеций. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

    Метод трапеций — метод численного интегрирования функции одной переменной, заключающийся в замене на каждом элементарном отрезке подынтегральной функции на многочлен первой степени, то есть линейную функцию. Площадь под графиком функции аппроксимируется прямоугольными трапециями.

    int main()

    {

    float a,b,n,h;//a и b - границы интегрирования, n - количество итераций

    cout<>a>>b>>n;

    h=(b-a)/n;//шаг итерации

    float I;

    I=(exp(sin(a))*sin(a)-exp(sin(b))*sin(b))/2;//Ваш интеграл от a и от b

    int i;

    for (i = 0; i I+=exp(sin(a+i*h))*sin(a+i*h);//тоже Ваш интеграл

    cout< getch();

    return 0;

    }

    15. Численное интегрирование методом парабол. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

    Геометрический смысл метода в том, что заменяем график функции на параболу, пересекающуюся с ним в концах и середине отрезка, а площадь криволинейной трапеции, соответственно, — на площадь под параболой. На многих других примерах можно столь же наглядно убедиться, сколь велико преимущество метода Симпсона над методами прямоугольников и трапеций в смысле точности результата. В то же время организация вычислений весьма проста, что и обуславливает широкое применение на практике этого метода.

    http://upload.wikimedia.org/wikipedia/commons/1/13/simpsons_method_illustration.png

    float f(float x)

    {float F;

    F=sin(x);

    return(F);

    };
    float SIMPSON(float a, float b, int n)

    {

    int i; float h,h2,x,s;

    h=(b-a)/n;

    h2=h/2;

    s=(f(a)+f(b))/2+2*f(a+h2);

    x=a;

    for(i=1;i {x=x+h;

    s=s+2*f(x+h2)+f(x);}

    s=s*h/3.0;

    return (s);

    }
    int main()

    {

    float rez;

    rez=SIMPSON(0,2,100);

    printf("%f",rez);

    }
    написать администратору сайта