6804

Автоматизация разметки блок-схем алгоритмов

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

Информатика, кибернетика и программирование

Автоматизация разметки блок-схем алгоритмов. Номер зачётной книжки: 831910 =100000011111112 Алгоритм обнаружения бесконечных циклов: Проверяем все операционные вершины на наличие перехода назад, если есть переход назад - помечаем блок д...

Русский

2013-01-08

84.4 KB

4 чел.

Автоматизация розметки блок-схем алгоритмов.

Номер зачётной книжки: 831910 =100000011111112;

Алгоритм обнаружения бесконечных циклов:

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

Иначе выводим сообщение о бесконечном цикле, и номер вершины в которой обозначен неверный переход.

Скриншоты программы:

Листинг программы:

import java.io.Serializable;

import java.util.ArrayList;

public class Algorithm implements Serializable{

 private static final long serialVersionUID = 1L;

 

 private int[][] mConnections;

 private int[][] mSignals;

 private ArrayList<String> signals;

 private boolean[] isY;

 

 public Algorithm(){}

 public Algorithm(int[][] mC, int[][] mS, ArrayList<String> signs){

 System.out.println("Connection matrix:  ");

 mConnections =mC;

 mSignals = mS;

 signals = signs;

 isY = new boolean[mC.length];

 for(int i = 0; i < mC.length; i ++){

 int sum = 0;

  for(int j = 0; j<mC.length;j++) {

   sum+= mC[i][j];

  }

  if(sum>1) isY[i] = false;

  else isY[i] = true;

 }

}

 public boolean isY(int i){

 return isY[i];

}

 

 public boolean checkInfinite(int from, int to) {

 if((to - from) == 1){return true;}

 for(int i = from; i < to; i++){

  if(isY(i)){

   if(fromTo(i)>to){ return false;}

   if(fromTo(i)<from){

    boolean inF = checkInfinite(fromTo(i), to);

    if(inF){return false;}

   }

  } else if(!isY(i)){

   if(fromTo_0(i)>to){ return false;}

   if(fromTo_0(i)<from){

    boolean inF = checkInfinite(fromTo(i), to);

    if(inF){return false;}

   }

   if(fromTo_1(i)>to){ return false;}

  }

 }

 return true;

}

 

 public String findInfiniteLoop(){

 String messageLine="algorithm is correct";

 int nNodes = mConnections.length;

 for(int out = 0; out < nNodes; out++){

  if(!isY(out)) continue;

  for(int in = 0; in < nNodes; in++){

   int current = mConnections[out][in];

   if((current==1)&&(out>in)){

    if(checkInfinite(in, out))

    messageLine = " infinite loop at  "+(out+1);

    return messageLine;

   }

  }

 }  

 return messageLine;

}

 

 public int fromTo(int from){

 int to=0;

 for(int i = 0; i<mConnections.length; i++) {

  if(mConnections[from][i]==1){ to = i+1; break; }

 }

 return to;

}

 

 public int fromTo_1(int from){

 return from+1;

}

 

 public int fromTo_0(int from){

 int to=0;

 for(int i = 0; i<mConnections.length; i++) {

  if((mConnections[from][i]==1)&&(i!=from)){ to = i+1; break; }

 }

 return to;

}

}


 

А также другие работы, которые могут Вас заинтересовать

27723. Смертная казнь как исключительная мера наказания по УП. Проблемы назначения и применения данного вида наказания 31 KB
  Смертная казнь как исключительная мера наказания по УП. Смертная казнь является исключительной мерой наказания которая заключается в лишении осужденного самого важного блага жизни. 277 295 317 и 357 УК РФ; сфера ее применения ограничена кругом лиц по полу и возрасту; смертная казнь в порядке помилования может быть заменена на пожизненное лишение свободы или лишение свободы на 25 лет; уголовноисполнительным законодательством установлен ряд дополнительных гарантий против исполнения необоснованных смертных приговоров: обязательна...
27725. Совершение преступления группой лиц, группой лиц по предварительному сговору, организованной группой лиц, преступным сообществом (преступной организацией) 29 KB
  Совершение преступления группой лиц группой лиц по предварительному сговору организованной группой лиц преступным сообществом преступной организацией. 35 Преступления совершенные группой лиц подразумевают только соисполнительство без предварительной договоренности о совершении преступления. При соисполнительстве не исключается распределение действий входящих в объективную сторону преступления между соучастниками. Как правило такие преступления совершаются в форме присоединения соисполнителя к противоправному посягательству уже...
27727. Террористический акт (ст. 205 УК) и заведомо ложное сообщение об акте терроризма (ст. 207 УК). Условия освобождения от уголовной ответственности за терроризм. Отличие данного преступления от диверсии 85.5 KB
  3 статьи характеризуется двумя формами вины прямым умыслом в отношении деяния и неосторожностью в отношении смерти человека или иных тяжких последствий. Угроза совершения взрыва поджога или иных действий устрашающих население и создающих опасность гибели человека причинения значительного имущественного ущерба либо наступления иных тяжких последствий часть 1 статьи 205 УК РФ может быть выражена различными способами например устное высказывание публикация в печати распространение с использованием радио телевидения или иных средств...
27728. Правовой статус иностранных граждан согласно Конституциям Монголии и Российской Федерации (сравнительно-правовое исследование) 50.5 KB
  УланБатор Правовой статус иностранных граждан согласно Конституциям Монголии и Российской Федерации сравнительноправовое исследование В двадцать первом веке веке глобализации мира люди могут свободно ездить работать учиться и жить в открытом обществе.1 Рассматривая вопрос о содержании правового статуса иностранных граждан в Монголии и Российской Федерации целесообразно использовать имеющиеся в юридической литературе наработки по общим проблемам правового положения личности поскольку статус иностранных граждан соотносится со статусом...
27729. Сравнительный анализ Конституции России и США 50.5 KB
  Конституция США не декларирует прав и обязанностей граждан. Декларация полномочий ветвей власти в Конституции США носит более абстрактный характер. Конституция США предусматривает выборную должность вицепрезидента в России эта должность упразднена.