Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 33   вперед  Ctrl
 решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
в теме "Почему ООП так популярно?" я затронул интересную олимпиадную задачку. вскоре на нее были даны различные варианты ответов... так вот выкладываю ниже свои и не только решения, хочу предложить всем заинтересовавшимся людям попробовать ее решить в том языке и тем способом, который они посчитают нужным, давайте померимся возможностью языков и методов, быть может неожиданно окроются плюсы или достоинства последних...


Задача------

Дан массив из K+L элементов. Нужно поменять местами две его части: 0..K-1 и K..K+L-1, не используя дополнительной памяти объёмом Z(K+L)за время O(K+L).
29 мар 09, 17:02    [6989750]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
первый мой вариант ранний
program ExgArr;

{$APPTYPE CONSOLE}

uses
  Windows, SysUtils;

const
   m = 10; // кол - во элементов в первом отрезке
   n = 1; // кол - во элементов во втором отрезке

var
  a: array[1..m + n] of Integer;
  i, l, k, t, q, r: Integer;

begin
{ инициализация массива             }
  for i := 1 to  m + n do
      a[i] := i;
{-------------------------------------------------------------------------------
Первый вариант обмена отрезков - суть в последовательном наложении первого
 отрезка на второй, в случае некратности первого второму выполняется перестановка
 отрезков полученных путем разбиения первого отрезка и так далее вплоть до
 полной перестановки
-------------------------------------------------------------------------------}
  i := 1;  // смещение в массиве
  k := 1;  // ссылка на границу первого отрезка
  l := m;  // начальная граница отрезков
  repeat
{*********************************************************
 *  выполняет перестановку отрезка                       *
 *  элементов m+1..n на место элементов отрезка i..m     *
 *  в массиве i..n.                                      *
 *  На входе:                                            *
 *    i - индекс первого элемента отрезка 1..l           *
 *    m + n - индекс последнего элемента отрезка l+1..m+n*
 *    m + n - const используется как константа           *
 *********************************************************}
    repeat
      t := a[i];
      a[i] := a[(l - k + 1) + i];
      a[(l - k + 1) + i] := t;
      i := i + 1
    until (((l - k + 1) + i) > (m + n));
{*********************************************************}
    {l := (m + n) - ((m + n) - l) mod (l - k + 1);}// высчитывание границы по методу
    q := m + n - l;                  // числа перекрытий второго отрезка первым
    r := l - k + 1;
    while (q >= r) do q := q - r;   // остаток будет смщением от конца масива
    l := m + n - q;
    k := i  // сохранение начала первого  отрезка в дальнейшем используется для
            // вычисления длины смещения перестановки эл-тов первого отрезка
  until (l = (m + n));

  for i := 1 to m + n do
    Write(a[i], ' ');
	  
{ инициализация массива             }
  for i := 1 to  m + n do
      a[i] := i;

{-------------------------------------------------------------------------------
Второй вариант  суть метода заключается в том что нужную перестановку двух
отрезков массива можно получить с помощью обратной перестановки всех эелементов
массива с последующей обратной перстановкой элементов отрезков
-------------------------------------------------------------------------------}
// перестановка элементов всего массива 1..m+n
  for i := 1 to ((m + n) div 2) do
    begin      
      t := a[i];
      a[i] := a[(m + n) - i + 1];
      a[(m + n) - i + 1] := t
    end;

// перестановка элементов отрезка 1..n
  for i := 1 to (n div 2) do
    begin
      t := a[i];
      a[i] := a[(n - i) + 1];
      a[(n - i) + 1] := t    
    end;
 
// перестановка элементов отрезка n+1..n+m
  for i := 1 to (m div 2) do
    begin
      t := a[n + i];
      a[n + i] := a[(m + n) + 1 - i];
      a[(m + n) + 1 - i] := t 
    end;



  for i := 1 to m + n do
      Write(a[i], ' '); 
  Readln;
end.
29 мар 09, 17:04    [6989752]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
более поздний переосмысленный
const
  K = 3;
  L = 7;

var
  massive: array[1..K+L] of Integer = (1,2,3,4,5,6,7,8,9,10);
  i: Integer;
  l_a, l_b: Integer;
  b_a, e_b: Integer;
  temp: Integer;

begin
  for i := 1 to K+L do
    Write(massive[i], ' ');
  Readln;
  
  l_a := K;
  l_b := L;
  b_a := 1;
  e_b := K + L;
  repeat
    i := 0;
    if l_a >= l_b then
      begin
        repeat
          temp := massive[b_a + l_a + i];
          massive[b_a + l_a + i] := massive [b_a + i];
          massive [b_a + i] := temp;
          i := i + 1
        until (i = l_b);
        l_a := l_a - l_b;
        b_a := b_a + l_b
      end
    else
      begin
        repeat
          temp := massive[e_b - l_a + 1 + i];
          massive[e_b - l_a + 1 + i] := massive[b_a + i];
          massive[b_a + i] := temp;
          i := i + 1
        until (i = l_a);
        l_b := l_b - l_a;
        e_b := e_b - l_a
      end
  until ((l_a = 0) or (l_b = 0));

  for i := 1 to K+L do
    Write(massive[i], ' ');
  Readln;
end.
29 мар 09, 17:09    [6989761]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Q
Guest
Даю ответ, придумайте загадку? :)
Я как чуть-чуть математик интересуюсь задачей сущестования. Существования формулировки задачи на естественном языке. :)
29 мар 09, 17:18    [6989769]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34387
автор
не могли бы вы господа решить данную задачу на любом из трех общепринятых языках(С, Бэйсик или Паскаль)...


Задача
------
Есть массив элементов(предположим целых чисел) mas[1] .. mas[K + L], рассматриваемый как объединие его отрезков: начала mas[1]..mas[K] длины K и mas[K+1].. mas[K+L] длины L. Не используя дополнительных структур данных для хранения отрезков, переставить их, т.е. первй -- в конец второй -- в начало. Алгоритм должен быть оптимальным.

Перевожу теперь на нормальный.


Задача
------
Дан массив из K+L элементов.
Нужно поменять местами две его части: 0..K-1 и K..K+L-1, не используя дополнительной памяти объёмом Z(K+L)
за время O(K+L).

Так ?
29 мар 09, 17:38    [6989799]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Q
Guest
А-а.
Какой параметр измеряем? "Кол-во перемещений элементов"? Сколько дается "свободных ячеек" для промежуточного хранения?
29 мар 09, 17:42    [6989807]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Q
Guest
И?

Тривиально доказуемо, что меньше, чем за K+L перемещений элементов это сделать нельзя. (T>=K+L)

Также тривиально, что при последовательном обходе всех циклов любой перестановки каждый элемент перемещается не более одного одного раза. (T<=K+L)

Несколько менее тривиально
-- cut here --
p будем считать циклическим сдвигом вправо на 1 позицию
pk == p * p ... *p -- последовательным применением p k раз
pK+L == 1 в этой группе
p -- примитивный элемент, его степени образуют все элементы циклической группы.
pL (то самое, необходимое нам преобразование массива) образует подгруппу с кол-вом элементов (K+L)/НОД((K+L), L) = (K+L)/НОД(K, L) => каждый цикл в результирующей перестановке имеет длину указанную в продолжении ниже
-- cut here --
доказуемо то, что количество циклов N = НОД (K, L) и длина их Q = (K+L)/НОД(K, L)
а также, что первые N (если, конечно, N > 1 :) ) элементов массива
(это можно и самостоятельно :) )
принадлежат разным циклам перестановки.

Выходит, что K+L, c одной временной ячейкой, и оптимальнее не существует. :)
29 мар 09, 20:00    [6990010]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
Q
И?

Тривиально доказуемо, что меньше, чем за K+L перемещений элементов это сделать нельзя. (T>=K+L)

Также тривиально, что при последовательном обходе всех циклов любой перестановки каждый элемент перемещается не более одного одного раза. (T<=K+L)

Несколько менее тривиально
-- cut here --
p будем считать циклическим сдвигом вправо на 1 позицию
pk == p * p ... *p -- последовательным применением p k раз
pK+L == 1 в этой группе
p -- примитивный элемент, его степени образуют все элементы циклической группы.
pL (то самое, необходимое нам преобразование массива) образует подгруппу с кол-вом элементов (K+L)/НОД((K+L), L) = (K+L)/НОД(K, L) => каждый цикл в результирующей перестановке имеет длину указанную в продолжении ниже
-- cut here --
доказуемо то, что количество циклов N = НОД (K, L) и длина их Q = (K+L)/НОД(K, L)
а также, что первые N (если, конечно, N > 1 :) ) элементов массива
(это можно и самостоятельно :) )
принадлежат разным циклам перестановки.

Выходит, что K+L, c одной временной ячейкой, и оптимальнее не существует. :)


спасибо MasterZiv за то что привел условие задачи...
про K+L вы наверно что-то напутали, либо я вас не допонял, последний вариант имеет минимальное число перестановок (K + L)/2 максимальное как раз K+L,
простейший тестовый вариант в доказательство моих слов в поседнем примере К = 5 L = 5 и посчитайте число перестановок... и я не ящу более оптимального решения этой задачи, я лишь хотел увидеть и оценить е реализации на различных языках...
29 мар 09, 20:21    [6990051]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
Q
А-а.
Какой параметр измеряем? "Кол-во перемещений элементов"? Сколько дается "свободных ячеек" для промежуточного хранения?

количество ячеек для промежуточного хранения минимально разумное - при обмене двух элементов не следут изголяться вычитаниями сложениями или перексориваниями, важнейший параметр конечно же количество перемещений... хотя мне более интересна реализация на других языках
29 мар 09, 20:26    [6990058]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Q
Guest
Для простоты я считал единицей работы ОДНО перемещение ОДНОГО элемента в ОДНОМ направлении.
:) Навроде того, как работает дефрагментация практически всего.
29 мар 09, 20:55    [6990117]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Q
Guest
Кстати, в реальной задаче, которая, разумеется, "без перексориваний" (дефрагментация диска произвольной заполненности, например), все равно потребуется два буфера в памяти: один под временное хранение данных кластера, другой, собственно для переписывания одного кластера в другой.
29 мар 09, 21:08    [6990144]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
SQL_Lamer
Member

Откуда: по колено в коде
Сообщений: 7454
Да пошла эта оптимизация...

arr = [4, 5, 6, 7, 8, 9, 1, 2, 3]
6.times {arr.push (arr.shift) }
29 мар 09, 22:30    [6990322]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Q
Guest
???
arr = [4, 5, 6, 7, 8, 9, 1, 2, 3]
arr = arr[6:]+arr[:6]
29 мар 09, 22:45    [6990372]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
SQL_Lamer
Member

Откуда: по колено в коде
Сообщений: 7454
Q
???
arr = [4, 5, 6, 7, 8, 9, 1, 2, 3]
arr = arr[6:]+arr[:6]


Чего изволите?
29 мар 09, 22:51    [6990379]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
SQL_Lamer
Member

Откуда: по колено в коде
Сообщений: 7454
Аа, дошло ...
29 мар 09, 22:51    [6990381]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
SQL_Lamer
Member

Откуда: по колено в коде
Сообщений: 7454
Q,

Ну аффтару же непременно перестановки были нужны
29 мар 09, 22:52    [6990386]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
SQL_Lamer
Member

Откуда: по колено в коде
Сообщений: 7454
Q
???
arr = [4, 5, 6, 7, 8, 9, 1, 2, 3]
arr = arr[6:]+arr[:6]


А так - то и мы могем

CL-USER> (setf arr (vector 4 5 6 7 8 9 1 2 3))
#(4 5 6 7 8 9 1 2 3)
CL-USER> (concatenate 'vector (subseq arr 6 9) (subseq arr 0 6))
#(1 2 3 4 5 6 7 8 9)
29 мар 09, 23:00    [6990404]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Q
Guest
$_ = "1,22,333,4444,55555,666666,7777777,88888888";
print $_."\n";s/^((\d+,){6})(.+)/\3,\1/;chop;print $_."\n";
29 мар 09, 23:27    [6990447]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
SQL_Lamer
Member

Откуда: по колено в коде
Сообщений: 7454
Q
$_ = "1,22,333,4444,55555,666666,7777777,88888888";
print $_."\n";s/^((\d+,){6})(.+)/\3,\1/;chop;print $_."\n";


Круто.
29 мар 09, 23:34    [6990456]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
Q
Для простоты я считал единицей работы ОДНО перемещение ОДНОГО элемента в ОДНОМ направлении.
:) Навроде того, как работает дефрагментация практически всего.


хм... я так и подумал, но тогда у меня получается какая - то нестыковочка, т.е. минимальное число перестановок всеравно (K+L)*3/2, так как одна перестановка равна 3 "физическим":)
29 мар 09, 23:43    [6990471]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
Q
$_ = "1,22,333,4444,55555,666666,7777777,88888888";
print $_."\n";s/^((\d+,){6})(.+)/\3,\1/;chop;print $_."\n";


а это на каком диалекте?) виуально похоже на струтуру типа список...
29 мар 09, 23:44    [6990472]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
SQL_Lamer
Q
???
arr = [4, 5, 6, 7, 8, 9, 1, 2, 3]
arr = arr[6:]+arr[:6]


А так - то и мы могем

CL-USER> (setf arr (vector 4 5 6 7 8 9 1 2 3))
#(4 5 6 7 8 9 1 2 3)
CL-USER> (concatenate 'vector (subseq arr 6 9) (subseq arr 0 6))
#(1 2 3 4 5 6 7 8 9)


а у вас что за язык? ну да) 29 строк паскаля против 3, круто конечно) этакими темпами програмисты скоро вообще программы писать не будут)
29 мар 09, 23:47    [6990476]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Q
Guest
Это PERL
на plain C тоже недолго:
#include <stdio.h>
int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, K = 6, L = 4;
int main()
{
  int N=K+L, i, j, Q, tmp; /* initial making sense value, will be changed in loop! */
  for(i=0; i<N; i++) {
    Q = 0;
    j=i;
    tmp = arr[j];
    do {
      printf("moving %d to %d\n", j, (j+L)%(K+L));
      tmp ^= (arr[(j+L)%(K+L)] ^= (tmp ^= arr[(j+L)%(K+L)]));
      j = (j+L)%(K+L);
      Q++; 
    } while(j != i);
    N = (K+L)/Q; /* calculate GCD(K, L) :) */
  }
  for(i=0; i<(K+L); i++)
    printf("%d\n", arr[i]);
  return 0;
}
29 мар 09, 23:55    [6990495]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
Q
Это PERL
на plain C тоже недолго:
#include <stdio.h>
int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, K = 6, L = 4;
int main()
{
  int N=K+L, i, j, Q, tmp; /* initial making sense value, will be changed in loop! */
  for(i=0; i<N; i++) {
    Q = 0;
    j=i;
    tmp = arr[j];
    do {
      printf("moving %d to %d\n", j, (j+L)%(K+L));
      tmp ^= (arr[(j+L)%(K+L)] ^= (tmp ^= arr[(j+L)%(K+L)]));
      j = (j+L)%(K+L);
      Q++; 
    } while(j != i);
    N = (K+L)/Q; /* calculate GCD(K, L) :) */
  }
  for(i=0; i<(K+L); i++)
    printf("%d\n", arr[i]);
  return 0;
}


да С это С... но вот конструкции
tmp ^= (arr[(j+L)%(K+L)] ^= (tmp ^= arr[(j+L)%(K+L)]));
меня убивают)
разбираться в чужом коде на С неимоверно тяжко... быть может просто нет привычки...
из всех вариантов пока, конечно, короткий и самый понятный для меня, не знающего этих языков ,это у SQL_Lamer. А вообще интересно наблюдать как можно решить задачу на другом неизвестном тебе языке...
30 мар 09, 00:11    [6990519]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Q
Guest
Ну, у вменяемых людей эта конструкция пишется так:
swap(&(arr[(j+L)%(K+L)]), &tmp);
но тут же конкурс извращений, не? :)
30 мар 09, 00:21    [6990542]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 33   вперед  Ctrl
Все форумы / Программирование Ответить