Сравнение пар вещественных чисел и выбор среди них минимального в каждой паре и максимума из них (Лабораторная работа № 2)

Министерство Образования Российской Федерации

Новосибирский Государственный Технический Университет

Лабораторная работа №2

По дисциплине: Структуры данных и алгоритмы

Выполнила

Студентка группы

ПМИ-31

Проверила:

Шапошникова Т.А.

г.Новосибирск

2004

Условие задачи

      7. Даны действительные числа   a₁ , a₂ ,   . . .  ,  a_2n   (n >= 2 и заранее неизвестно). Вычислить:

      в)  max ( min ( a₁ , a_2n ) , min ( a₃ , a_2n-2 ) ,  . . .  , min ( a_2n-1 , a₂ ) )  .

Анализ задачи

Дано:  - последовательность чисел, причем

Результат:

Исходя из такой постановки задачи, алгоритм ее решения очевиден. Это сравнение пар вещественных чисел и выбор среди них сначала минимального в каждой паре, а затем максимума из них. В формализованном виде выглядит так:

Однако с учетом требований к реализации мы обязаны реализовать все это с помощью двунаправленного списка. Воспользуемся для этого двунаправленным некольцевым списком без заглавного звена. Кроме того учтем, что при вводе чисел нам необходимо будет определять символ конца вводимой последовательности. Обозначим его точкой. Тогда алгоритм ввода данных и добавления элемента в список будет выглядеть следующим образом:

reading = 1;

n=0;

ПОКА (reading=1)

            Ввод с

            ЕСЛИ c='.'

reading=0;

            ИНАЧЕ

                        ЕСЛИ (n=0)

                                    Создать первый элемент списка (head – указатель)

                                    Объявить предыдущий элемент head пустым

                                    P=head

                        ИНАЧЕ

                                    Создать элемент, следующий за p

                                    Объявить p предыдущим для своего следующего

                                    Сместить указатель p на следующий элемент

                        Записать в p значение c

                        N=N+1

end=p;

end = последний элемент

А алгоритм вычисления заданного выражения так:

p1=head;

p2=end;

max=min(head.x,end.x);

ПОКА (p1 не последний элемент)

            t=min(p1.x,p2.x);

            ЕСЛИ (t>max)

max=t;

            p1=следующий за следующим элементом за p1

            p2= следующий за следующим элементом за p2

Мы проверяем, условие завершения по p1 так как оно совпадает и с условием завершения по p2 поэтому не имеет смысла проверять их оба.

Блок схема программы

Текст программы

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

//Структура элемента списка

struct elem {

      float x;

      elem * next;

      elem * prev;

};

//Функция определяющая минимальное из двух чисел

float min(float x, float y) {

      if(x<y)return x;

      return y;

}

void main() {

      printf("Vvedite posledovatelnost: ");

      elem * head,* end,*p;

      int reading = 1;

      int n=0;

      char c[10];

      while(reading) {

            scanf("%s",c);

            //Проверяем на конец строки

            if(c[0]=='.')reading=0;

            else {

                  //Преобразуем строку в число

                  float x = atof(c);

                  if(n==0) {

                        head=end=p=new elem;

                        head->prev=NULL;

                  } else {

                        p->next = new elem;

                        p->next->prev=p;

                        p=p->next;

                  }

                  p->x=x;

                  n++;

            }

      }

      end=p;

      end->next=NULL;

      //Если число элементов последовательности нечетно – выводим сообщение об ошибке

      if(n%2==1) {

            printf("\nError!\n");

      } else {

            elem *p1=head;

            elem *p2=end;

            float max=min(head->x,end->x);

            float t;

            while(p1) {

                  t=min(p1->x,p2->x);

                  if(t>max)max=t;

                  p1=p1->next->next;

                  p2=p2->prev->prev;

            }

            printf("Result: %f\n",max);

      }

      getch();

}

Тестирование программы

№	Цель	Исх. Данные	Результат
1	Проверка на ввод некорректных данных	1 2 3 .	Error!
2	Проверка на ввод целых значений последовательности	1 2 3 4 5 6 7 8 9 10 .	5
3	Проверка на ввод вещественных значений	1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0 .	1.5
4	Общий тест	7 15 8 6 2 4 9 1.248 2 3	6