powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / решение тривиальной алгоритмической задачи разными подходами и средствами
25 сообщений из 812, страница 1 из 33
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35898946
студентик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
в теме "Почему ООП так популярно?" я затронул интересную олимпиадную задачку. вскоре на нее были даны различные варианты ответов... так вот выкладываю ниже свои и не только решения, хочу предложить всем заинтересовавшимся людям попробовать ее решить в том языке и тем способом, который они посчитают нужным, давайте померимся возможностью языков и методов, быть может неожиданно окроются плюсы или достоинства последних...


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

Дан массив из K+L элементов. Нужно поменять местами две его части: 0..K-1 и K..K+L-1, не используя дополнительной памяти объёмом Z(K+L)за время O(K+L).
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35898947
студентик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
первый мой вариант ранний
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
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.
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35898954
студентик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
более поздний переосмысленный
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
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.
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35898961
Q
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Q
Гость
Даю ответ, придумайте загадку? :)
Я как чуть-чуть математик интересуюсь задачей сущестования. Существования формулировки задачи на естественном языке. :)
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35898983
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
авторне могли бы вы господа решить данную задачу на любом из трех общепринятых языках(С, Бэйсик или Паскаль)...
Код: plaintext
1.
2.
3.
Задача
------
Есть массив элементов(предположим целых чисел) mas[1] .. mas[K + L], рассматриваемый как объединие его отрезков: начала mas[1]..mas[K] длины K и mas[K+1].. mas[K+L] длины L. Не используя дополнительных структур данных для хранения отрезков, переставить их, т.е. первй -- в конец второй -- в начало. Алгоритм должен быть оптимальным.

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

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

Так ?
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35898988
Q
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Q
Гость
А-а.
Какой параметр измеряем? "Кол-во перемещений элементов"? Сколько дается "свободных ячеек" для промежуточного хранения?
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35899095
Q
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Q
Гость
И?

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

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

Несколько менее тривиально
-- cut here --
p будем считать циклическим сдвигом вправо на 1 позицию
p k == p * p ... *p -- последовательным применением p k раз
p K+L == 1 в этой группе
p -- примитивный элемент, его степени образуют все элементы циклической группы.
p L (то самое, необходимое нам преобразование массива) образует подгруппу с кол-вом элементов (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 одной временной ячейкой, и оптимальнее не существует. :)
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35899124
студентик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
QИ?

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

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

Несколько менее тривиально
-- cut here --
p будем считать циклическим сдвигом вправо на 1 позицию
p k == p * p ... *p -- последовательным применением p k раз
p K+L == 1 в этой группе
p -- примитивный элемент, его степени образуют все элементы циклической группы.
p L (то самое, необходимое нам преобразование массива) образует подгруппу с кол-вом элементов (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 и посчитайте число перестановок... и я не ящу более оптимального решения этой задачи, я лишь хотел увидеть и оценить е реализации на различных языках...
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35899129
студентик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
QА-а.
Какой параметр измеряем? "Кол-во перемещений элементов"? Сколько дается "свободных ячеек" для промежуточного хранения?
количество ячеек для промежуточного хранения минимально разумное - при обмене двух элементов не следут изголяться вычитаниями сложениями или перексориваниями, важнейший параметр конечно же количество перемещений... хотя мне более интересна реализация на других языках
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35899166
Q
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Q
Гость
Для простоты я считал единицей работы ОДНО перемещение ОДНОГО элемента в ОДНОМ направлении.
:) Навроде того, как работает дефрагментация практически всего.
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35899178
Q
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Q
Гость
Кстати, в реальной задаче, которая, разумеется, "без перексориваний" (дефрагментация диска произвольной заполненности, например), все равно потребуется два буфера в памяти: один под временное хранение данных кластера, другой, собственно для переписывания одного кластера в другой.
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35899258
Фотография SQL_Lamer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Да пошла эта оптимизация...

Код: plaintext
1.
2.
arr = [ 4 ,  5 ,  6 ,  7 ,  8 ,  9 ,  1 ,  2 ,  3 ]
 6 .times {arr.push (arr.shift) }
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35899272
Q
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Q
Гость
???
Код: plaintext
1.
arr = [ 4 ,  5 ,  6 ,  7 ,  8 ,  9 ,  1 ,  2 ,  3 ]
arr = arr[ 6 :]+arr[: 6 ]
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35899273
Фотография SQL_Lamer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Q???
Код: plaintext
1.
arr = [ 4 ,  5 ,  6 ,  7 ,  8 ,  9 ,  1 ,  2 ,  3 ]
arr = arr[ 6 :]+arr[: 6 ]


Чего изволите?
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35899274
Фотография SQL_Lamer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Аа, дошло ...
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35899278
Фотография SQL_Lamer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Q,

Ну аффтару же непременно перестановки были нужны
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35899288
Фотография SQL_Lamer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Q???
Код: plaintext
1.
arr = [ 4 ,  5 ,  6 ,  7 ,  8 ,  9 ,  1 ,  2 ,  3 ]
arr = arr[ 6 :]+arr[: 6 ]


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

Код: plaintext
1.
2.
3.
4.
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 )
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35899317
Q
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Q
Гость
$_ = "1,22,333,4444,55555,666666,7777777,88888888";
print $_."\n";s/^((\d+,){6})(.+)/\3,\1/;chop;print $_."\n";
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35899323
Фотография SQL_Lamer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Q$_ = "1,22,333,4444,55555,666666,7777777,88888888";
print $_."\n";s/^((\d+,){6})(.+)/\3,\1/;chop;print $_."\n";

Круто.
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35899332
студентик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
QДля простоты я считал единицей работы ОДНО перемещение ОДНОГО элемента в ОДНОМ направлении.
:) Навроде того, как работает дефрагментация практически всего.

хм... я так и подумал, но тогда у меня получается какая - то нестыковочка, т.е. минимальное число перестановок всеравно (K+L)*3/2, так как одна перестановка равна 3 "физическим":)
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35899333
студентик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Q$_ = "1,22,333,4444,55555,666666,7777777,88888888";
print $_."\n";s/^((\d+,){6})(.+)/\3,\1/;chop;print $_."\n";

а это на каком диалекте?) виуально похоже на струтуру типа список...
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35899334
студентик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SQL_LamerQ???
Код: plaintext
1.
arr = [ 4 ,  5 ,  6 ,  7 ,  8 ,  9 ,  1 ,  2 ,  3 ]
arr = arr[ 6 :]+arr[: 6 ]


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

Код: plaintext
1.
2.
3.
4.
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, круто конечно) этакими темпами програмисты скоро вообще программы писать не будут)
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35899343
Q
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Q
Гость
Это PERL
на plain C тоже недолго:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
#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 ;
}
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35899357
студентик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
QЭто PERL
на plain C тоже недолго:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
#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 ;
}


да С это С... но вот конструкции
Код: plaintext
tmp ^= (arr[(j+L)%(K+L)] ^= (tmp ^= arr[(j+L)%(K+L)]));
меня убивают)
разбираться в чужом коде на С неимоверно тяжко... быть может просто нет привычки...
из всех вариантов пока, конечно, короткий и самый понятный для меня, не знающего этих языков ,это у SQL_Lamer. А вообще интересно наблюдать как можно решить задачу на другом неизвестном тебе языке...
...
Рейтинг: 0 / 0
решение тривиальной алгоритмической задачи разными подходами и средствами
    #35899370
Q
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Q
Гость
Ну, у вменяемых людей эта конструкция пишется так:
Код: plaintext
swap(&(arr[(j+L)%(K+L)]), &tmp);
но тут же конкурс извращений, не? :)
...
Рейтинг: 0 / 0
25 сообщений из 812, страница 1 из 33
Форумы / Программирование [игнор отключен] [закрыт для гостей] / решение тривиальной алгоритмической задачи разными подходами и средствами
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]