Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #21  
Старый 18.01.2009, 17:29
гость

 
Сообщений: n/a

а можно подробнее именно про динамику?
  #22  
Старый 14.05.2009, 10:01
гость

 
Сообщений: n/a

Здравствуйте.
А в виде блок-схемы можно этот алгоритм написать. А то с питоном, я думаю не все знакомы.
  #23  
Старый 14.05.2009, 11:15
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Могу привести перевод на Паскаль, однако или у меня ошибка вкралась, или фикс в питоновском коде не все учел, и с наборами типа [1,2,2], 2 есть повторы :
1 | 2 2 |
1 2 | 2 |
1 2 | 2 |
  #24  
Старый 14.05.2009, 11:34
гость

 
Сообщений: n/a

Если можно. Буду премного благодарен.
  #25  
Старый 14.05.2009, 12:03
гость2

 
Сообщений: n/a

[quote]Могу привести перевод на Паскаль, однако или у меня ошибка вкралась, или фикс в питоновском коде не все учел, и с наборами типа [1,2,2], 2 есть повторы :[/uqote]
Вот полный код, и он повторов не выдаёт:
Код:
#!/usr/bin/python2.6
# coding: utf-8
import sys

def generate_multi_partitions(values, K, func):
    N = len(values)
    values = sorted(values)
    avail = [True for each in range(N)]
    output = [[] for each in range(K)]

    def foo(k):
        if k >= 2 and output[k-2] > output[k-1]:   # (лексикографическое сравнение списков)
            return
        if k == K-1:
            output[k] = []
            for i in range(N):
                if avail[i]:
                    output[k].append(values[i])
            if len(output[k]) > 0 and (k == 0 or output[k-1] <= output[k]):
                func(output)
            output[k] = []
        else:
            for i in range(N):
                if avail[i]:
                    bar(k, i)
                    return

    def bar(k, i):
        output[k].append(values[i])
        avail[i] = False
        foo(k+1)
        for j in range(i+1, N):
            if avail[j] and (j == 0 or values[j-1] != values[j] or not avail[j-1]):
                bar(k, j)
        output[k].pop()
        avail[i] = True

    foo(0)


generate_multi_partitions([1,2,2], 2, lambda p: sys.stdout.write('%s\n' % p))

Цитата:
А в виде блок-схемы можно этот алгоритм написать.
Блок-схемы? Разве кто-то их еще использует?
Я их последний раз видел в книжках кнута почти сороколетней давности...

Цитата:
А то с питоном, я думаю не все знакомы.
Это очень простой язык, практически псевдокод, но только его еще можно и запустить на выполнение.
Рекомендую всем с ним ознакомиться.
  #26  
Старый 14.05.2009, 12:36
гость

 
Сообщений: n/a

[quote=
Это очень простой язык, практически псевдокод, но только его еще можно и запустить на выполнение.
Рекомендую всем с ним ознакомиться.[/QUOTE]

А кроме Питона есть еще не один десяток хороших и простых языков. Но в каждом своя идеология, свои заморочки, плюсы и минусы. У кождого свои приверженцы и противники. Свои встроенные функции и свои типы данных. Поэтому алгоритмы принято писать в языконезависимом виде.
Но если не будет другой возможности, то видимо придется садиться за учебники:-)
Хотя подожду пока вариант на Паскале.
  #27  
Старый 14.05.2009, 13:24
гость

 
Сообщений: n/a

Цитата:
Поэтому алгоритмы принято писать в языконезависимом виде.
В пользу написания алгоритмов на конкретном языке программирования хочу заметить что их можно легко запускать и тестировать сразу на конкретных компьютерах, а вот этот "языконезависимый вид" никак сразу непотестируешь, и его приходится каждый раз переводить в конкретный язык. Что занимает время, да есть возможность ошибиться при таком переводе.

Даже Кнут кроме псевдокода еще приводит и реализацию многих своих алгоритмов на MMIX.

Цитата:
А кроме Питона есть еще не один десяток хороших и простых языков
Ну, например, Python сейчас использует MIT (лучший тех. вуз мира) на вводном курсе по программированию. А в гугле это scripting language of choice.
  #28  
Старый 14.05.2009, 13:46
гость

 
Сообщений: n/a

Как вот на конкретно моем компьютере запустить приведенный выше код?
  #29  
Старый 14.05.2009, 14:24
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

ага, с исправлениями в bar повторы ушли.
Тупой перевод на Дельфи, вместо списков строки, числа однозначные в десятичной записи (обусловлено использованной заменой pop - строкой с Delete, но это нетрудно доработать)

Код:
//разбиение мультимножества (сортированный массив чисел со значениями < 10) на KP частей
  procedure generate_multi_partitions(values: array of Integer; KP: Integer);
  var
    N, i: Integer;
    avail: array of Boolean;
    output: array of string;

    procedure foo(k: Integer); forward;

    procedure bar(k, i: Integer);
    var
      j: Integer;
    begin
      output[k] := output[k] + IntToStr(values[i]) + ' ';
      avail[i] := False;
      foo(k + 1);
      for j := i + 1 to N - 1 do
        if avail[j] and ((j = 0) or (values[j - 1] <> values[j]) or (not avail[j
          - 1])) then
          bar(k, j);
      Delete(output[k], Length(output[k]) - 1, 2);
      avail[i] := True;
    end;

    procedure foo(k: Integer);
    var
      i, j: Integer;
      s: string;
    begin
      if (k >= 2) and (output[k - 2] > output[k - 1]) then
        Exit;
      if k = KP - 1 then begin
        output[k] := '';
        for i := 0 to N - 1 do
          if avail[i] then
            output[k] := output[k] + IntToStr(values[i]) + ' ';
        if (Length(output[k]) > 0) and ((k = 0) or (output[k - 1] <= output[k]))
          then begin
          s := '';
          for j := 0 to KP - 1 do
            s := s + output[j] + ' | ';
          Memo1.Lines.Add(s);// или Writeln(s) для консольного приложения
        end;
        output[k] := '';
      end
      else
        for i := 0 to N - 1 do
          if avail[i] then begin
            bar(k, i);
            Exit;
          end;
    end;

  begin
    N := Length(values);
    SetLength(avail, N);
    SetLength(output, KP);
    for i := 0 to N - 1 do
      avail[i] := True;
    foo(0);
  end;

begin
  generate_multi_partitions([1, 2, 2, 2, 3], 3);
end;
  #30  
Старый 14.05.2009, 14:31
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Как вот на конкретно моем компьютере запустить приведенный выше код?
Сохрани его в любой файл и введи в командной строке "python <имя этого файла>". В современных юниксах питон обычно уже установлен по умолчанию; а под windows - тебе нужно скачать и установить дистрибутив с http://www.python.org. (А еще лучше будет установить cygwin чтобы получить полностью юникс-подобную среду)
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Нахождение множества элементарных циклов графа kilobait Графы 9 17.03.2008 10:02
Покрытие множества кругами Tolran Вычислительная геометрия 3 29.11.2007 01:00
алгоритм нахождения минимального множества сечений контуров обратной связи ikro Графы 0 03.05.2007 11:00
разбиение плоскости фигурами ASH Вычислительная геометрия 1 17.03.2007 15:13
разбиение прямоугольника helium Вычислительная геометрия 5 03.03.2007 11:24