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;

}

}


 

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

23449. Секретная служба в тылу немцев (1914 - 1918 гг.) 1.97 MB
  В 1913 году закончил колледж Гонвилла и Кейюса в Кембридже и собирался продолжить учебу чтобы стать горным инженером но с началом Первой мировой войны пошел добровольцем на фронт сначала служил в медицинской службе потом в полевой артиллерии где дослужился до капитана. Тем не менее они отмечали что в книгах содержится ряд неточностей и что автор порой слишком преувеличивал свои заслуги. Если мне не придётся больше быть в Голландии то я всё же буду помнить что дорога из Роттердама в Амстердам через Гаагу и Гарлем ровная а вокруг...
23450. История гитлерюгенда 404.5 KB
  История гитлерюгенда Введение ХХ век далеко не случайно считается эпохой тоталитаризма. У части западных историков сложилось восприятие гитлерюгенда как организации автономной от НСДАП и государственных органов Третьего Рейха. Поэтому несомненно что в большинстве своем члены гитлерюгенда свободны от вины за преступления совершенные нацистами. Но несмотря на всё это надо объективно рассматривать историческую роль гитлерюгенда так как он был организацией вполне интегрированной в политическую систему Третьего Рейха.
23451. Алфавитно-справочный перечень государей русских и замечательнейших особ их крови 4.98 MB
  АГАФИЯ великая княгиня Так некоторые известия именуют жену Всеволода II Ольговича великого князя киевского сообщая что она выдана за него в 1116 г. 189 и родила мужу сыновей Святослава князя киевского и Ярослава князя черниговского да еще дочь Звениславу за Болеславом IV герцогом польским. АГАФИЯ ВСЕВОЛОДОВНА великая княгиня жена по Татищеву вторая великого князя Юрия Георгия II Всеволодовича великого князя владимирского дочь Всеволода Святославича Чермного князя черниговского одно время великого князя киевского от...
23453. Древние майя. Загадки погибшей цивилизации 2.28 MB
  Древние майя. Кто создал эти колоссы Когда С какой целью Что вызвало к жизни блестящую цивилизацию майя в саном центре гиблых тропических джунглейАвтор книги на основе новейших данных о древнеамериканской истории рассматривает ряд таинственных событий далекого прошлого индейцев майя. Гуляева это древнейшие судьбы Мезоамерики важнейшего и глубоко своеобразного региона одного из первых очагов производящего хозяйства высокой и оригинальной цивилизации индейских народностей майя сапотеков нахуа. Гуляев назвал ее Древние...
23454. Георгий Константинович Жуков Воспоминания и размышления 10.56 MB
  Скоро мы узнали что в Питере 9 января 1905 года царские войска и полиция расстреляли мирную демонстрацию рабочих которая шла к царю с петицией просить лучших условий жизни. После Нижегородской ярмарки в том же году пришлось поехать на другую ярмарку в Урюпино в Область Войска Донского. Я всегда восхищался этим романтическим родом войск. От раненых мы многое узнали и в первую очередь то что наши войска очень плохо вооружены.
23455. Третий Рим 14.12 MB
  Ведь ему известно что русские были сторонниками христианской Византии и противниками мусульманской Турции. Следуя тезису о богоустановленном единстве всего христианского мира Филофей доказывал что первым мировым центром был Рим старый за ним Рим новый Константинополь а в последнее время на их месте стал третий Рим Москва. Не надо думать что это какаято гипербола или метафора. Филофей ясно подчеркивает что речь идет об объединении всех христианских царств под властью великого князя Василия.
23456. ПРАВДА ВИКТОРА СУВОРОВА 3.84 MB
  Он гласит: СССР всегда последовательно боролся за мир. Смена статуса сталинского СССР с жертвы и освободителя на статус палача и агрессора тяжело дается даже людям не испытывающим симпатий к сталинизму. Даже если они специалисты по истории СССР. И тем более если они советские специалисты по военной истории СССР.
23457. Красные партизаны Украины 1941-1944 3.2 MB
  На обложке: Целлюлознобумажная фабрика сожжённая партизанами соединения им. Коротченко в верхнем ряду второй слева с партизанами Тернопольского соединения им. Соединения партизан которые посылали в эти регионы чтобы они с помощью агитации получали поддержку выслеживались и уничтожались 11. ИЗ ОПЕРАТИВНОГО ОТЧЁТА КОМАНДИРА СУМСКОГО ПАРТИЗАНСКОГО СОЕДИНЕНИЯ С.