2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Последовательность, на которой алгоритм зациклится
Сообщение20.04.2013, 13:33 
Добрый день. Есть следующее задание:

Дана функция:

Код:
function incorrect(array[])
  for i = 0 to length(array)
    if (array[i] > i) then
      j = i
      while (j < length(array)) and (array[j] >= j)
        j = j + 1
      temp = array[i]
      array[i] = array[j]
      array[j] = temp
      i = 0


Каково минимальное N , что существует такая перестановка чисел от 0 до N-1 , на которой алгоритм работает бесконечно?

Моя интерпретация на С :

Код:
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int a[]={3,1,2,0};
    int n=4;
    int i=0;
    int j;
    int temp;
    for(i=0;i<n;i++)
    {
        if(a[i]>i)
        {
            j=i;
            while((j<n)&&(a[j]>=j))
            {
                j++;
            }
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
            i=0;
        }
   
    }
    return 0;
}


Правда есть одно "но": в моём коде, элемент с нулевым индексом рассматривается только один раз, до первой перестановки, не уверен, что авторы задачи это подразумевали.

Буду благодарен за любую помощь, заранее спасибо

..............

Извиняюсь, был уверен, что пишу в корень.

 
 
 
 Re: Последовательность, на которой алгоритм зациклится
Сообщение26.04.2013, 08:47 
Аватара пользователя
Neud в сообщении #713125 писал(а):
Правда есть одно "но": в моём коде, элемент с нулевым индексом рассматривается только один раз, до первой перестановки, не уверен, что авторы задачи это подразумевали.

А замена в 22 строке i = 0; на i = -1; не поможет?

-- 26 апр 2013, 09:55 --

Neud в сообщении #713125 писал(а):
j=i;
while((j<n)&&(a[j]>=j))
{
j++;
}

Предпочитаю
Код:
for(j = i; j < n && a[j] >= j; j++);
Но это не существенно, всего лишь вопрос стиля.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group