Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Анализ ошибок в последовательности точек

Автор: kjf03 7.8.2010, 16:46

   Доброе время суток.

   Исходные данные: - робот в цикле обходит периодически точки (от 1 до N; обход должен быть 1->2->..->N->1->2->..->N->1->..);
                                  - началом нового периода считается точка №1;

   Необходимо подсчитать количество ошибок в периоде (1->2->..->N) допущенные роботом.
   Ошибкой в периоде считать:
                        - пропущена точка;
                        - нарушена последовательность (1->2->3->5->4->6->7->8  в данной последовательности 5 и 4 считать
                          нарушением последовательности, то есть необходимо учитывать восстановление последовательности).
   Замечанием в периоде считать:
                        - посещение точки более 1 раза, каждое лишнее посещение замечание.

  Подскажите как лучше реализовать алгоритм анализа обхода точек робота?

Автор: nworm 7.8.2010, 16:58

Код


error=0;
for(i=1,j=1;j<=N;i++,j++)
  {
     if (a[j]!=i)
       {
           if (a[j]>i) 
            {
              error++;
              if ((a[j]==i+1)&&(a[j+1]==i)) j=j+2;//перестановка
              if ((a[j]==i+1)&&(a[j+2]==i+2) j=j+1;//пропуск точки
            }
       }
  }

Как-то так или усложнить этот код.

Автор: Akina 7.8.2010, 19:02

Недоопределённое условие.

Пример:
1->2->3->5->4->5->6->7->8
Это может трактоваться и как только лишнее посещение, и как нарушение последовательности плюс лишнее посещение.

Пока не будет абсолютной строгости формулировки задания - не будет и решения.

Автор: kjf03 7.8.2010, 19:32

Цитата(Akina @ 7.8.2010, 19:02)

ошибки и замечания независимо друг от друга считаются.

В реализации nworm не реализован подсчет замечаний.

Автор: kjf03 7.8.2010, 20:05

Замечанием в периоде считать:
- посещение точки более 1 раза, причем подряд- это замечание. При посещении точки повторно, но не подряд - это ошибка.

Автор: Akina 7.8.2010, 21:47

Цитата(kjf03 @ 7.8.2010, 20:32

)

ошибки и замечания независимо друг от друга считаются.

Думай, потом пиши...
Повторяю.
1->2->3->5->4->5->6->7->8
Вариант 1 - базовая последовательность 1->2->3->5->4->5->6->7->8. Ошибка нарушения последовательности есть.
Вариант 2 - базовая последовательность 1->2->3->5->4->5->6->7->8. Ошибка нарушения последовательности отсутствует.

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

Автор: kjf03 7.8.2010, 23:56

Цитата(Akina @ 7.8.2010, 21:47)

Цитата(kjf03 @ 7.8.2010, 20:32

)

ошибки и замечания независимо друг от друга считаются.

Вариант 1 - базовая последовательность 1->2->3->5->4->5->6->7->8. Ошибка нарушения последовательности есть.
Вариант 2 - базовая последовательность 1->2->3->5->4->5->6->7->8. Ошибка нарушения последовательности отсутствует.

1->2->3->5->4->5->6->7->8
                 ^   ^  ^
                  |    |   |_ошибка повторное посещения точки (если бы было 3->5->5->4->5->6, то вторая 5 трактовалась как замечание)
                  |    |_ ошибки нет, восстановление последовательности.
                  |_ошибка - нарушение последовательности.

   Ошибкой в периоде считать:
                        - пропущена точка;
                        - нарушена последовательность (1->2->3->5->4->6->7->8  в данной последовательности 5 и 4 считать
                          нарушением последовательности, то есть необходимо учитывать восстановление последовательности);
                        - повторное посещение точки, при условии что предыдущая точка отлична от текущей;
                        - восстановление последовательности возможно при выполнении следующего условия: номер точки
                          восстановления последовательности, должен быть больше последнего номера точки до нарушения последовательности.
   Замечанием в периоде считать:
                        - посещение точки более 1 раза, при условии что предыдущая точка идентична текущей.

Автор: Akina 8.8.2010, 19:58

Иными словами, базовая последовательность состоит из ПЕРВЫХ посещений каждой точки.
Тогда ошибки пропуска и замечания повторного посещения определяются в ходе (пропуск - по завершении) сортировки подсчётом, а ошибки нарушения последовательности - сравнением базовой последовательности с эталонной.
Я бы предложил двухпроходный алгоритм - на первом проходе определяются и ВЫБРАСЫВАЮТСЯ из последовательности замечания повтора, на втором проходе по очищенной последовательности - выявляются ошибки нарушения последовательности, а по завершении любого из проходов - получается список ошибок пропуска.