Описание Алгоритма программы

Мурманский филиал Петровского Колледжа

Курсовая

По дисциплине

«Компьютерное моделирование»

На тему

«Транспортная задача»

Выполнил: Ошкин Е.С.

Проверил: Сергеев А.В.

Мурманск

Г.

Описание Алгоритма программы

ПРОГРАММА НАПИСАНА НА BORLAND С++ версии 3.1

Программа решает Транспортную Задачу (ТЗ) 3 методами:

1. Северо-западным углом

2. Северо-восточным углом

3. Методом минимального элемента в строке.

Программа состоит из функций:

1. Main()

2. Data()

3. Opplan()

4. Sohran()

5. Bas()

6. Kost()

7. Potenzial()

8. Optim()

9. Plmi()

10. Abcikl()

11. Cikl()

12. Prpoisk()

13. Levpoisk()

14. Verpoisk()

15. Nizpoisk()

16. Pr()

Главная функция main() невелика, но в ней происходит обращение функциям, выполняющим определенные действия в процессе решения ТЗ. Здесь следует обратить особое внимание на строку программы if(!z) break; - если бы не она (она показывает, что после очередной проверки базисного плана, если он оптимален, возвращаемое значение из функции optim() равно 0, что приводит к выходу из бесконечного цикла улучшения базисных планов). Иногда возникает ситуация, когда базисная переменная(одна или несколько) равна нулю, и ее следует отличать от других базисных переменных. В матрице matr() такие элементы я пометил как –2. Основные переменные я описал в комментариях в программе.

Функция data() производит ввод данных на ТЗ.

Функция opplan() выполняет задачи по составлению первоначального базисного плана методом северо-заподного угла. В этой функции используются следующие переменные:

Int *matr указатель на матрицу базисных переменных

Int *po указатель на вектор пунктов отправления

Int *pn указатель на вектор пунктов назначения

Int m количество пунктов отправления

Int n количество пунктов назначения

Функция kost() производит вывод суммарной стоимости перевозок по текущему базисному плану. Используются следующие переменные:

Int *matr, m,n;

Int *st указатель на матрицу стоимостей.

Функция potenzial() выполняет подсчет потенциалов.

Использует следующие переменные:

Int *pu указатель на вектор потенциалов строк

Int *pv указатель на вектор потенциалов столбцов

Int matr, m, n, *st;

Первоначально элементы векторов потенциалов *(pu+i) и *(pv+j) заполняются минимальными значениями для целых переменных = 32768, определенных предпроцессорным оператором define MIN – 32768. Далее пологая, что *pu=0, и используя структуру struct poten{…}, элементы векторов потенциалов приобретают свои реальные значения.

Работу этого модуля я бы разделил на эти этапы:

· Выделение памяти под элемент структуры top = (struct poten*)malloc(sizeof(struct poten)); заполнение полей элемента структуры необходимой информацией; установление связей между элементами структуры;

· Вычисление потенциалов строк и столбцов с занесением информации в секторы pu и pv;

· Проверка правильности заполнения векторов pu и pv, т.е. установление не содержат ли элементы этих векторов значения MIN. При необходимости, если существуют такие элементы векторов, производятся дополнительные вычисления;

· Вывод векторов pu и pv;

  Функция optim() проверяет план на оптимальность, если он оптимален, то функция отправляет в главную функцию main() значение 0, в противном случае, если он не оптимален, то управление передается функции abcikl() и возврат главной функции main() значение –1. Функция optim() использует переменные:

 Int m,n,*pu,*pv, *matr, *st. Цепь строится относительно первой попавшейся графоклетки, для которой u_i + v_j =c_ij , а не относительной характеристики. В ходе решения ТЗ промежуточные базисные планы отличаются от тех, которые я построил, начиная с координат графоклетки с минимальным значением отрицательной характеристики, но врезультате оптимальный план будет тот же.

Функция abcicl() – использует следующие переменные

 Int *matr, m, n;

Int *matr2 //указатель на рабочую (изменяемую) матрицу, по началу она является копией оригинальной.

Int ik,jk; // координаты графоклетки, с которой начинает строиться цепь. В этой функции присваивается графоклетки, с которой будет происходить поиск цикла(цепь), значение -1.

Функция cikl() производит поиск относительно графоклетки со значением –1. Она использует следующие переменные:

Int *matr2, ik, jk;

Int ch; // счетчик количества элементов в массивах *zi и *zj

Int *zi, *zj // указатели на массивы индексов. Хранят индексы элементов matr, подлежащих перераспределению.

 

Функции prpoisk(), levpoisk(), verpoisk(), nizpoisk()-поиск, соответственно, вправо, влево, вверх, вниз – относительно текущей графоклетки. Поиск происходит в массиве *matr2. Если известна строка, то выполняется поиск столбца, т.е. его индекса, если известен столбец –ищется строка.

Данные функции возвращают координаты столбца или строки найденной графоклетки, либо значение –1, если графоклетка в данном направлении не найденна.

Работа модуля cikl() заключается в следующем:

· Поиск нужного элемента начинается относительно графоклетки, помеченной –1 в матрице matr2 (с координатами ik и jk согласно входным данным) по возможным направлениям (поочередно);

· Если поиск успешен, то поля структуры заполняются информацией, найденный элемент структуры включается в список(работу модуля поддерживает линейный список, в котором хранится информация о ходе поиска цепи), и за основу берется уже эта (текущая) графоклетка матрицы matr2(). Далее процедура поиска повторяется:

· Если поиск на каком-то шага не неуспешен по возможным направлениям, то найденный элемент исключается из списка и за основу берется последний элемент списка (после удаления). В рабочей матрице matr2() «обнуляется» элемент с координатами, который хранил исключенный элемент, что необходимо для того, чтобы исключить повторное обращение к элементу matr2, не входящемму в цепь;

· Поиск цикла (цепи) будет закончен, когда при прохождении по какому-либо направлению мы снова наткнемся на элемент матрицы matr2 со значением –1. В конце модуля элементы списка, т.е. его поля с координатами, переписываются в векторы zi и zj.

Внешние переменные:

Int m, n, *matr2;

Входные данные:

Int i1, j1 // координаты текущей графоклетки, относительно которой строится цепь.

Выходные данные:

I(j)- координаты строки, столбца, если переменная найдена;

Функция pr(), осуществляет печать текстовых сообщений о ходе поиска в матрице; она вызывается из модуля cikl().

Функция plmi() перераспределяет поставки по цепи, т.е. улучшает план.

  Используются следующие переменные:

 Int zi,zj;

Int ch,chr; /переменные размерности массивов zi,zj

Int matr /указатель на матрицу базисных переменных

Работа с модулями выполняется в несколько этапов. Если имеется нулевой базисный элемент (помеченный как –2 в матрице matr) и индекс k нечетен для векторов zi,zj, то элементы matr, помеченные, как –1 и –2(новый элемент помеченный как –2 обнуляем), меняются местами, в противном случае(если k четно или нет нулевых базисных элементов в matr) осуществляется:

Нахождение минимального элемента в матрице базисных переменных: min=matr [i][j], где i=zi[k]; j=zj[k]; k-нечетное число;

Перераспределение поставок:

       a) если k четное число, то matr[i][j] = matr[i][j]+min, где i=zi[k]; j=zj[k];

       b)если k нечетное число, то matr[i][j] = matr[i][j]-min, где i=zi[k]; j=zj[k];

 

 

Модуль bas() подсчитывает количество ненулевых базисных переменных в матрице matr.

Модуль sohran() находит нулевую базисную переменную в matr и устанавливает её в –2.

Int basper; /количество базисных переменных.

Функция opplan1() построение первоначального плана методом северо-восточного угла, а opplan2()- методом выбора наименьшего элемента в строке.

          Ниже приведен текст программы

#include <stdio.h> //Подключение стандартных

#include <alloc.h> // Библиотек

#include <conio.h>

#include <process.h>

#include <stdlib.h>

#define MIN -32768

 

 

int *po = NULL; //Указатель на массив пунктов отправления

int *pn = NULL; //Указатель на массив пунктов назначения

int *st = NULL; //Указатель на матрицу стоимостей

int *matr=NULL; //Указатель на матрицу базисных переменных

int *matr2 = NULL; //Указатель на рабочую матрицу

int n ,m;      //Размерность задачи

int *pu,*pv;    //Указатели на массивы потенциалов

int *zj,*zi;   // Указатель на массивы индексов

int ch=0,ch2=0; //Счетчики

FILE *fpdat;   //Указатель на вводной файл

int iter=0; //Счетчик итерации

FILE *fil;  //Указатель на выводной файл

int zen = -1; //Переменная для сохранения стоимости п-на

int z = 1; //Флаг для выхода при оптимальном плане

int basper;

 

 // void exit(int status);

 

 

   void data(void)

       {

       int i,j,t;

       printf("Введите количество складов: ");

       scanf("%d",&m);

       printf("Kolichestvo skladov-----> %d",m);

       printf("\n Введите количество магазинов:\n");

       scanf("%d",&n);

       printf("\n Kolichestvo magazinov --->%d",n);

       //*********** Выделение памяти ******************

       if((po=(int*)calloc(m,sizeof(int)))==NULL) abort();

       if((pn=(int*)calloc(n,sizeof(int)))==NULL) abort();

       if((st=(int*)calloc(n*m,sizeof(int)))==NULL) abort();

 

       printf("Введите элементы матрицы стоимостей: \n");

       for(i=0;i<m;i++)

             {

             for(j=0;j<n;j++)

             {

             printf("Введите [%d][%d]\n ",i,j);

             scanf("%d",&t);

                   *(st+i*n+j)=t;

 

             }

             }

             printf("\n");

             fprintf(fil,"\n");

             for(i=0;i<m;i++)

             {

             for(j=0;j<n;j++)

                   {

                   printf("%5d",*(st+i*n+j));

                   fprintf(fil,"%5d",*(st+i*n+j));

                   }

             printf("\n");

             fprintf(fil,"\n");

             }

             printf("Введите количество запасов на каждом складе:\n");

             for(i=0;i<m;i++)

                   {

                   printf("\n");

                   scanf("%d",po+i);

                   printf("%5d",*(po+i));

                   }

             printf("\n");

             printf("Введите потребности:\n");

                    for(j=0;j<n;j++)

                         {

                        printf("\n");

                         scanf("%d",pn+j);

                         printf("%5d",*(pn+j));

                         }

                         return;

                         }//**** data

 

//************* SOZDANIE OPORNOGO PLANA ********************

//************* METHOD NORD-WEST YGLA **********************

void opplan(void)

       {

       int i,j,ch1 = 0;

       //*************** ВЫДЕЛЕНИЕ ПАМЯТИ *************************

       if((matr=(int*)calloc(m*n,sizeof(int))) == NULL) abort();

 

// ЦИКЛ ПРОСТОГО РАСПРЕДЕЛЕНИЯ ПОТРЕБНОСТЕЙ по ячейкам рабочей матрицы

       for(i=0;i<m;i++)

       {

       for(j=ch1;j<n;j++)

             {

             if(*(po+i)<*(pn+j))

                    {

                    *(matr+i*n+j)=*(po+i);

                    *(pn+j)-=*(po+i);

                    *(po+i)=0;

                    break;

                    }

                    *(matr+i*n+j)=*(pn+j);

                    *(po+i) -= *(pn+j);

                    *(pn+j)=0;

                    ch1++;

                    }

              }

//********* ПРОВЕРКА И ВЫвод получившейся матрицы ***********************

        printf("PROVERKA\n");

        fprintf(fil,"PROVERKA MATRIX - Северо заподный УГОЛ,\n просмотр получившегося распределения в матрице \n");

        for(i=0;i<m;i++)

       {

       for(j=0;j<n;j++)

             {

             printf("%5d",*(matr+i*n+j));

             fprintf(fil,"%d",*(matr+i*n+j));

             }

             printf("\n");

             fprintf(fil,"\n");

             }

                        fprintf(fil,"********************\n");

                        return;

                        } // opplan

 

 

       void kost(void)

                   {

                   int i,j, *matr1,rez=0;

                   //выделение памяти

                   if((matr1=(int*)calloc(n*m,sizeof(int))) == NULL) abort();

             //присвоение новой матрице значения базисной(старой) матрицы

                   for(i=0;i<m;i++)

                   {

                   for(j=0;j<n;j++)

                        {

                        *(matr1+i*n+j) = *(matr+i*n+j);

                        }

                   }

 

              // Подсчет стоимости базисной матрицы (созданного массива)

                   for(i=0;i<m;i++)

                        {

                        for(j=0;j<n;j++)

                               {

                               if(*(matr1+i*n+j)>0)

                                    rez += (*(matr1+i*n+j)) *(*(st+i*n+j));

                               }

                        }

                   printf("\n Rezultat : %d",rez);

                   printf("\n");

                   fprintf(fil,"%s %5d"," Rezultat : ",rez);

                   fprintf(fil,"\n");

             getch();

                   free(matr1);

                   if(zen == rez)

                   {

                   z=0;

                   }

                   zen = rez;

                   return;

                    }

       //************* KOST()

 

       //************* PODSCHET POTENCIALOV ********************

 

       void potenzial(void)

       {

       struct poten

             {

             int v;

             int u;

             int zn;

             struct poten *next;

             int b;

             } *topnast = NULL,

             *top = NULL,

             *top1 = NULL;

 

             int i,j;

             int fl;

 

//********** ВЫДЕЛЕНИЕ ПАМЯТИ *******************8

if((pu=(int*)calloc(m,sizeof(int)))==NULL) abort();

if((pv=(int*)calloc(n,sizeof(int)))==NULL) abort();

// ПРИСВОЕНИЕ ВСЕМ ПОТЕНЦИАЛАМ ЗНАЧЕНИЯ MIN

for(i=0;i<m;i++)

        *(pu+i) = MIN;

 

for(j=0;j<n;j++)

        *(pv+j) = MIN;

 // Выделение памяти под структуру и заполнение её значениями

for(i=0;i<m;i++)

        {

        for(j=0;j<n;j++)

             {

             if((*(matr+i*n+j) > 0) || (*(matr+i*n+j)==-2))

                   {

                   if((top=(struct poten*)malloc(sizeof(struct poten)))==NULL)

                   abort();

                   fprintf(fil,"top = %d",top);

                   if(!topnast){

                   topnast = top;

                   fprintf(fil,"topnast = top = %d",top);

              }

                   else top1 -> next=top;

                         top1=top;

                         top -> next=NULL;

                         top -> b = *(st+i*n+j); //Стоимости

                         top -> v = j;

                         top -> u = i;

                         top -> zn = -1;

                         }

                   }

              }

       *pu = 0;

       i=0; j = -1;

       for(top = topnast;top!=NULL;top = top -> next)

             {

                   if((top -> u) == i && (top -> v)!=j)

                   {

                         *(pv+(top -> v)) = (top -> b) - *(pu+i);

                         j = (top->v);

                         top -> zn = 0;

                   }

                   else{

                   for(top1 = topnast;top1 != NULL;top1 = top1->next)

                         {

                        if((top1->v) == j && (top1->u)!=i)

                              {

                               *(pu+(top1->u))=(top1->b) - *(pv+j);

                               i = (top1->u);

                               top1 ->zn = 0;

                         break;

                              }

                        }

                         }

                   }

// ********** Продолжение функции подсчета потенциалов *****************

 

for(;;){

       fl = 0;

       for(top = topnast;top!=NULL;top =top -> next)

              {

              if((top -> zn) == -1)

             {

             if(*(pu+(top ->u)) !=MIN)

                   {

                   *(pv+(top->v))=(top->b) - *(pu+(top ->u));

                   fl = 1;

                   top -> zn = 0;

                   }

             if(*(pv+(top->v)) !=MIN)

                   {

                   *(pu+(top->u))=(top->b) - *(pv+(top->v));

                   fl=1;

                   top->zn = 0;

                   }

             }

             }

             if(!fl) break;

             }

             printf("\n ПОТЕНЦИАЛЫ ПО v:");

             fprintf(fil,"\n **** ПОТЕНЦИАЛЫ ПО v:");

             for(i = 0;i<n;i++)

             {

             printf("%d",*(pv+i));

             fprintf(fil,"%5d",*(pv+i));

             }

             getch();

             printf("\n ПОТЕНЦИАЛЫ ПО u: ");

             fprintf(fil,"\n **** ПОТЕНЦИАЛЫ ПО u: ");

             for(i=0;i<m;i++)

             {

             printf("%d",*(pu+i));

             fprintf(fil,"%5d",*(pu+i));

             }

             fprintf(fil,"\n");

             for(top = topnast;top!=NULL;top = top->next)

                   free(top);

                   return;

                   } // potenzial

 

 

// ****** PROVERKA PLANA NA OPTIMALNOST' ************************

                    void abcikl(int ik,int jk);

                    int cikl(int ik,int jk);

                    void pr(char pr[],void *st); // Предварительно

                    int prpoisk(int i1,int j1); // Объявлены

                    int levpoisk(int i1,int j1); //ЭТИ

                    int verpoisk(int i1,int j1); //Функции

                    int nizpoisk(int i1,int j1);

int optim(void)

       {

       int i,j;

       for(i=0;i<m;i++)

       {

       for(j=0;j<n;j++)

              {

// ИЩЕМ ОПТИМАЛЬНОЕ РЕШЕНИЕ В НАШЕЙ МАТРИЦЕ И ЕСЛИ ЕГО НЕ НАЙДЕМ

// ТО ПО СЛЕДУЮЩЕМУ УСЛОВИЮ ПРИСВОИМ ГРАФОКЛЕТКЕ С КООРДИНАТАМИ

// ik,jk ЗНАЧЕНИЕ -1

              if(( *(pu+i)+ *(pv+j))>(*(st+i*n+j))&&((*(matr+i*n+j)) == 0))

                    {

                    abcikl(i,j);

                    fprintf(fil,"optim(): План не оптимален, функции main() возвращаем -1,\n а abcikl() параметры i,j ");

                    return(-1);

                    }

              }

       }

        fprintf(fil,"Plan optimalen");

        return(0);

} // ******* optim() ***************

 

// ************** UPGRADE PLAN **************************

void abcikl(int ik,int jk)

{

int i,j;

fprintf(fil,"Мы в abcikl()");

if((matr2=(int*)calloc(n*m,sizeof(int))) == NULL) abort();

for(i=0;i<m;i++)

       {

       for(j=0;j<n;j++)

       {

       *(matr2+i*n+j) = *(matr+i*n+j); // Создаем копию рабочей матрицы

       }

       }

       *(matr2+ik*n+jk) = -1;

 // значению матрицы с параметрами ik,jk присваеваем -1

 

       printf("\n");

 

       printf("Поиск Цепи: \n\n");

       fprintf(fil,"Поиск Цепи: \n\n");

       for(i=0;i<m;i++)

       {

       for(j=0;j<n;j++)

             {

             fprintf(fil,"%5d",*(matr2+i*n+j));

             printf("%5d",*(matr2+i*n+j));

             }

             fprintf(fil,"\n");

             printf("\n");

       }

              fprintf(fil,"\n\n Переходим в Сраную, Мать её, Функцию cikl(ik,jk) \n");

       getch();

       cikl(ik,jk);

 

       return;

       } // abcikl

 

// ********* FUNKCION POISKA CIKLA **************************

int cikl(int ik,int jk)

       {

       int nst,nstr,i,j,

             perlev = 0,

             perpr = 0;

       int perver = 0,

             perniz = 0,

             fl = 0,

             fl3 = 1;

       int napr;

 

       struct cik { int prnapr;

                    int ick;

                         int jck;

                         struct cik *next;

                   } *topnast1 = NULL,

                         *top2 = NULL,

                         *top3 = NULL;

                    ch = 0;

             if((top2 = (struct cik*)malloc(sizeof(struct cik))) == NULL)

             abort();

 

             if(!topnast1)

             {

             topnast1=top2;

             top3=top2;

             top3->ick=ik;

             top3->jck=jk;

             }

             else

             top3->next=top2;

             top3=top2;

             top2->next=NULL;

             top2->ick = ik;

             top2->jck = jk;

             ch++;

             fprintf(fil,"\n\nДо Условия while fl3 =%d \n",fl3);

             pr("top2",top2);

             fprintf(fil,"Весь цикл поиска сейчас начнется, надеюсь - \n что он будет не бесконечный или не бесполезный :( \n");

             printf("Весь цикл поиска сейчас начнется, надеюсь - \n что он будет не бесконечный или не бесполезный :( \n");

             printf("\n \t \t\tpress anykey to contunio\n");

             getch();

             while(fl3)

                   {

                   fl3=0;

                   fl = 0;

                   if((nst = prpoisk(ik,jk))>=0)

                   {

                   fprintf(fil,"\n\nВнимание!!!\n nst = %d \n",nst);

                   fprintf(fil,"Ща будет поик идти ему бы...:Point found!\n");

                   printf("И он пошел RIGHT:Point found !\n\r");

                   napr = 2;

                   jk = nst;

                   top2->prnapr = 1;

                   }

             else if((nstr = nizpoisk(ik,jk))>=0)

                   {

                   fprintf(fil,"DOWN: Point found !\n");

                   printf("DOWN: Point found !\n\r");

                   napr = 3;

                   ik = nstr;

                   top2->prnapr = 2;

                   }

 

                   else if((nst=levpoisk(ik,jk))>=0)

                        {

                        fprintf(fil,"LEFT:Point found !\n");

                        printf("LEFT:Point found !\n\r");

                        napr = 4;

                        jk = nst;

                        top2->prnapr = 3;

                        }

// **************** Prodolzhenie 1 poiska ***********************

        else if((nstr = verpoisk(ik,jk))>=0)

             {

             fprintf(fil,"UP:Point found !\n");

             printf("UP:Point found !\n\r");

             napr = 1;

             ik = nstr;

             top2->prnapr = 4;

             }

             else

             return(-1);

 

        while(!fl || *(matr2+ik*n+jk)!=-1)

              {

              fl=1;

              switch(napr)

                   {

                   case 1:

                         printf("Search to the right --->");

                         fprintf(fil,"Search to the right --->");

                         if((nst = prpoisk(ik,jk))>=0)

                              {

                              printf("founded\n\r");

                              fprintf(fil,"founded\n");

                              if((top2=(struct cik*)malloc(sizeof(struct cik)))==NULL)

                          abort();

                              if(!topnast1) topnast1=top2;

                              else top3 -> next=top2;

                                     top3 = top2;

                                     top2 -> next = NULL;

                                     top2->ick = ik;

                                     top2->jck = jk;

                                     ch++;

                                     top2->prnapr = 1;

                                     pr("top2",top2);

                                     napr = 2;

                                     jk = nst;

                                     perpr = perlev = 0;

                                     } // **** IF *******

                              else

                              {

                              fprintf(fil,"Point not found ! Change direction to LEFT\n");

                              napr = 3;

                              perpr = 1;

                              }

                   break;

//***************** PRODOLZHENIE 2 POISKA ******************************

              case 2:

              printf("Search to the down --->");

              fprintf(fil,"Search to the down --->");

              if((nstr=nizpoisk(ik,jk))>=0)

                   {

                   if((top2=(struct cik*)malloc(sizeof(struct cik))) == NULL)

                   abort();

                   printf("founded\n\r"); fprintf(fil,"founded\n");

                   if(!topnast1) topnast1=top2;

                   else top3->next=top2;

                   top3=top2;

                   top2->next=NULL;

                   top2->ick = ik;

                   top2->jck = jk;

                   ch++;

                   top2->prnapr = 2;

                   pr("top2",top2);

                   napr = 3;

                   ik = nstr;

                   perniz=perver=0;

                   } //**** IF ********

                   else

                        {

                        fprintf(fil,"Point not found ! Change direction to UP\n");

                        napr = 4;

                        perniz = 1;

                        }

                        break;

 

             case 3:

                    printf("Search to the left -->");

                    fprintf(fil,"Search to the left -->");

                        if((nst=levpoisk(ik,jk))>=0)

                              {

                              if((top2=(struct cik*)malloc(sizeof(struct cik))) == NULL)

                                          abort();

                                          printf("founded\n\r"); fprintf(fil,"founded\n");

                                          if(!topnast1)

                                                 topnast1=top2;

                                                      else

                                                      top3->next=top2;

                                                      top3=top2;

                                                      top2->next=NULL;

                                                      top2->ick = ik;

                                                      top2->jck = jk;

                                                      ch++;

             //************ PRODOLZHENIE 3 POISKA *************

                              top2->prnapr = 3;

                              pr("top2",top2);

                              napr = 4; jk = nst;

                              perlev = perpr = 0;

                              } // ******* IF *****

                              else{

                              fprintf(fil,"Point not found ! Change direction to RIGHT\n");

                              napr = 1;

                              perlev = 1;

                              }

                              break;

             case 4:

             printf("Search to the up --->");

             fprintf(fil,"Search to the up --->");

             if((nstr=verpoisk(ik,jk))>=0)

                   {

                   if((top2=(struct cik*)malloc(sizeof(struct cik)))==NULL)

                         abort();

                   printf("founded\n\r"); fprintf(fil,"founded\n");

                   if(!topnast1) topnast1=top2;

                   else top3->next=top2;

                   top3=top2;

                   top2->next=NULL;

                   top2->ick=ik;

                   top2->jck=jk;

                   ch++;

                   top2->prnapr = 4;

                   pr("top2",top2);

                   napr = 1;

                   ik = nstr;

                   perver = perniz = 0;

                   } // *****If **************

                   else

                    {

                    fprintf(fil,"Point not found ! Change direction to DOWN\n");

                    napr = 2;

                    perver = 1;

                    }

                    break;

                    } // ************ SWITCH ********************

        // ************** PRODOLZHENIE 4 POISKA ********************

              if(perlev == 1 && perpr == 1)

                   {

                   *(matr2+ik*n+jk) = 0;

                   ik = top3 ->ick;

                   jk = top3 ->jck;

                   napr = top3->prnapr;

                   top3 = topnast1;

                   printf("Zerro 1\n\r");

 

                   for(top2=topnast1;top2->next !=NULL;top2=top2->next)

                   top3 = top2;

                   top3 -> next=NULL;

                   perlev = perpr = 0; // if(ch == 1)

                   if(top2==top3)

                   {

                   fl3=1;

                   break;

                   }

                   else

                   {

                   top3->next=NULL;

                   free(top2);

                   ch--;

              printf("Viynimaem tochky: (%d,%d)=%d\n",ik,jk,*(matr2+ik*n+jk));

                   fprintf(fil,"Viynimaem tochky: (%d,%d)=%d\n",ik,jk,*(matr2+ik*n+jk));

                   pr("top2",top2);

                   }

             perpr = 0;

             perlev = 0;

                   } // IF

 

                   if(perver == 1 && perniz == 1)

                   {

                   *(matr2+ik*n+jk)=0;

                   printf("Zerro 2\n\r");

                   ik=top3->ick;

                   jk = top3->jck;

                   napr = top3->prnapr;

                   top3 = topnast1;

 

                   for(top2 = topnast1;top2->next !=NULL;top2=top2->next)

                        top3 = top2; perver = perniz = 0;

                        if(top2==top3)

                        {

                        fl3=1;

                        break;

                        }

                        else

                               {

                               top3->next = NULL;

                               free(top2);

                               ch--;

// ******* PRODOLZHENIE 5 POISKA *********************

        printf("Viynimaem tochky: (%d,%d) = %d\n",ik,jk,*(matr2+ik*n+jk));

        fprintf(fil,"Viynimaem tochky: (%d,%d) = %d\n",ik,jk,*(matr2+ik*n+jk));

 

             pr("top2",top2);

             }

             perver = 0;

             perniz = 0;

             } // IF

             if(ch==0)

             {

             fl3=1;

             break;

       }

             } //while

       } //while

       i=0;

       if((zi = (int*)calloc(ch,sizeof(int))) == NULL ) abort();

       if((zj = (int*)calloc(ch,sizeof(int))) == NULL ) abort();

             printf("\n\r");

             ch2 = ch;

             for(top2 = topnast1;top2 !=NULL;top2 = top2->next)

             {

             *(zi+i) = top2 ->ick;

             *(zj+i) = top2 ->jck;

             i++;

             }

 

             return(0);

             } // *********** cikl ****************************

 

                   int prpoisk(int i1, int j1)

             {

             int j;

 

             for(j=j1+1;j<n;j++)

             {

             if((*(matr2+i1*n+j))!=0)

                    return(j);

                    }

                    return(-1);

                    }

       int levpoisk(int i1,int j1)

             {

             int j;

 

             for(j = j1-1;j>=0;j--)

             {

             if((*(matr2+i1*n+j))!=0)

             return(j);

             }

              return(-1);

              }

       int verpoisk(int i1,int j1)

       {

       int i;

 

       for(i=i1-1;i>=0;i--)

             {

             if((*(matr2+i*n+j1))!=0)

             return(i);

             }

             return(-1);

             }

 

       int nizpoisk(int i1, int j1)

             {

             int i;

             for(i = i1+1;i<m;i++)

                   {

                   if((*(matr2+i*n+j1))!=0)

                   return(i);

                   }

                   return(-1);

                   }

 

                   // ************* FUNCTION SEARCH ********************

void pr(char pr[],void *st)

       {

       struct cik { int prnapr;

                         int ick;

                         int jck;

                         struct cik *next;

                         } *ptr;

       int i,j;

 

       ptr = (struct cik *)st;

       fprintf(fil,"Koordinatiy ytoplennoy tochki : %d and %d",ptr->ick,ptr->jck);

       printf("Koordinatiy ytoplennoy tochki : %d and %d\n\r",ptr->ick,ptr->jck);

       fprintf(fil,"and napravlenie");

       printf("Napravlenie");

       switch(ptr->prnapr)

       {

       case 1:

             fprintf(fil,"Vpravo\n");

             printf("Vpravo\n\r");

             break;

       case 2:

             fprintf(fil,"Vniz\n");

             printf("Vniz\n\r");

             break;

       case 3:

             fprintf(fil,"Vlevo\n");

             printf("Vlevo\n\r");

             break;

       case 4:

             fprintf(fil,"Vverh\n");

             printf("Vverh\n\r");

             break;

       default:

             fprintf(fil,"Start\n");

             printf("Start\n\r");

             break;

       }

       fprintf(fil,"WORK MATRIX\n");

       for(i=0;i<m;i++)

       {

       for(j=0;j<n;j++)

             {

             fprintf(fil,"%5d",*(matr2+i*n+j));

             }

             fprintf(fil,"\n");

             }

             fprintf(fil,"************************************\n");

             return;

       }

 

 

// **************** UPGRADE PLAN *********************************//

void plmi(void)

       {

       int i,j,k,min,i1,j1,flagok;

       ch = ch2;

       flagok = 0;

       i1=*zi;

       j1 = *zj;

       for(k=1;k<ch;k+=2){

             i=*(zi+k);

             j = *(zj+k);

             if(*(matr+i*n+j) == -2){

             *(matr+i1*n+j1) = *(matr+i*n+j);

             *(matr+i*n+j) = 0;

             flagok = 1;

             break;

             }

             } // for

             if(!flagok){

             for(k=2;k<ch;k+=2){

                   i = *(zi+k);

                   j = *(zj+k);

                   if(*(matr+i*n+j) == -2)

                   *(matr+i*n+j) = 0;

             } // for

             i = *(zi+1);

             j = *(zj+1);

             min = *(matr+i*n+j);

             for(k=3;k<ch;k+=2){

                   i=*(zi+k);

                   j=*(zj+k);

                   if(*(matr+i*n+j)<min)

                   min = *(matr+i*n+j);

             }

             if(min == -2) min = 0;

             for(k=0;k<ch;k+=2){

                    i = *(zi+k);

                    j = *(zj+k);

                    *(matr+i*n+j) += min;

             }

             for(k=1;k<ch;k+=2){

                   i=*(zi+k);

                   j=*(zj+k);

                   *(matr+i*n+j)-=min;

                   }

              } //if

// ***************** PROVERKA **************************//

 

printf("PROVERKA\n");

for(i=0;i<m;i++){

 for(j=0;j<n;j++){

printf("%5d",*(matr+i*n+j));

 }

 printf("\n");

}

free(matr2);free(zi);free(zj);free(pu);free(pv);

return;

}

 

 

void Bas(void)

{

int i,j;

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

       {

       if(*(matr+i*n+j)!=0) basper++;

       }

}

return;

}

 

void sohran(void)

{

// Sravnenie

int i,j,k;

for(k=0;k<ch;k++)

        {

        i=zi[k];

        j=zj[k];

        if((*(matr+i*n+j) == 0) && (basper < m+n-1))

       {

       *(matr+i*n+j) = -2;

       basper++;

       }//if

        }

       return;

       }

 // ************ SOZDANIE OPORNOGO PLANA **************************

 // ************ METODOM SEVERNO-ZAPADNOGO YGLA *******************

 void opplan1(void)

{

int i,j, ch1 = n-1;

//**************** Viydelenie pamyty *************************

if((matr=(int*)calloc(m*n,sizeof(int))) == NULL) abort();

 for(i=0;i<m;i++)

       {

       for(j=ch1;j>=0;j--)

       {

       if(*(po+i)<*(pn+j))

              {

              *(matr+i*n+j)=*(po+i);

              *(pn+j)-=*(po+i);

              *(po+i)=0;

              break;

              }

              *(matr+i*n+j)=*(pn+j);

              *(po+i)-=*(pn+j);

              *(pn+j)=0;