Форум портала г. Королёва :: Просмотр темы - Помогите с алгоритмами
 ФотоальбомФотоальбом FAQFAQ   ПоискПоиск   ПользователиПользователи   ГруппыГруппы   РегистрацияРегистрация   Доска объявленийДоска объявлений    ПрофильПрофиль   Войти и проверить личные сообщенияВойти и проверить личные сообщения   ВходВход 
Помогите с алгоритмами
На страницу Пред.  1, 2, 3, 4  След.
Начать новую тему   Ответить на тему    Список форумов Форум портала г. Королёва -> Наука и Жизнь
Предыдущая тема :: Следующая тема  
Автор Сообщение
Nouzui



Зарегистрирован: 07.06.2005
Сообщения: 310

СообщениеДобавлено: 26 Дек 2006, 13:24    Заголовок сообщения: Ответить с цитатой

Dwarflord писал(а):
Кому не лень подумать, просьба помочь.
Подумать тут требуется.

Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение.

Формат входных данных
Первая строка входного файла содержит заданный шаблон длиной не более 80 символов.

Формат выходных данных
Выведите в выходной файл искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2*10^9.

Пример
input.txt output.txt

????(? 2

жесть
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
PGM



Зарегистрирован: 24.10.2003
Сообщения: 68
Откуда: Королев

СообщениеДобавлено: 26 Дек 2006, 15:04    Заголовок сообщения: Ответить с цитатой

Dwarflord писал(а):
Кому не лень подумать, просьба помочь.

Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение.

Есть сразу решение "в лоб". Предположим что все знаки есть вопросы - генерируем все валидные комбинации скобок заданной длины (что не очень сложно), а затем сверяем их с входной маской и отбрасываем те, что не подошли по расположению уже установленных скобок. В результате останется искомое.

Более оптимизированное решение, вероятно, рекурсивный алгоритм с анализом 2-х первых и 2-х последних символов с отбрасыванием 2 с начала, 1+1 или 2 с конца в зависимости от выполнения условий и применением того же алгоритма к оставщейся строке с подсчетом "возможных" ветвлений.

В условиях не сказано, все ли вопросы должны быть заменены - если все, то перым делом, естественно, проверям четность количества символов. Если нет - алгоритмы будут более изощренными, так как вопросы можно пропускать в любом месте. Но если судить по твоему примеру, то все-таки все вопросы должны быть заменены, иначе ответ в примере неверен - вместо 2 ответ будет 8.
_________________
"Не ботфортом консомэ хлебаем"
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
S@dkyn



Зарегистрирован: 12.01.2005
Сообщения: 23

СообщениеДобавлено: 26 Дек 2006, 16:21    Заголовок сообщения: Ответить с цитатой

Dwarflord писал(а):


PGM писал(а):

Есть сразу решение "в лоб". Предположим что все знаки есть вопросы - генерируем все валидные комбинации скобок заданной длины (что не очень сложно), а затем сверяем их с входной маской и отбрасываем те, что не подошли по расположению уже установленных скобок. В результате останется искомое.


Это-то всё понятно. Сам хотел так делать. Однако затормозился на том, как посчитать кол-во вариантов, если даже будут одни знаки вопроса.


PGM писал(а):

В условиях не сказано, все ли вопросы должны быть заменены - если все, то перым делом, естественно, проверям четность количества символов. Если нет - алгоритмы будут более изощренными, так как вопросы можно пропускать в любом месте. Но если судить по твоему примеру, то все-таки все вопросы должны быть заменены, иначе ответ в примере неверен - вместо 2 ответ будет 8.


Про чётность тоже ясно. Должны быть заменены все знаки вопроса.


Вернуться к началу
Посмотреть профиль Отправить личное сообщение
PGM



Зарегистрирован: 24.10.2003
Сообщения: 68
Откуда: Королев

СообщениеДобавлено: 27 Дек 2006, 14:39    Заголовок сообщения: Ответить с цитатой

Dwarflord писал(а):

Это-то всё понятно. Сам хотел так делать. Однако затормозился на том, как посчитать кол-во вариантов, если даже будут одни знаки вопроса.


Ну теорией заниматься откровенно лень, а вот программку, пожалуйста. Вроде работает, правда рекурсивная, но тут главное - идея, а в итеративную можно переделать если объем данных велик.

Код:

procedure Generate(Size: Integer; LS: TStrings);
var i : Integer; LSX : TStringList;
begin
  if Size <= 2 then begin
    LS.Add('()');
    Exit;
  end;

  LSX := TStringList.Create;
  Generate(Size-2, LSX);
  for i := 0 to LSX.Count-1 do LS.Add('('+LSX[i]+')');
  for i := 0 to LSX.Count-1 do LS.Add('()'+LSX[i]);
  LSX.Free;
end;

.....
// ну и вызов начальный для длины 10 например
Generate(10, Memo.Lines);
.....

_________________
"Не ботфортом консомэ хлебаем"
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Nouzui



Зарегистрирован: 07.06.2005
Сообщения: 310

СообщениеДобавлено: 27 Дек 2006, 19:24    Заголовок сообщения: Ответить с цитатой

http://homepages.compuserve.de/chasluebeck/practic_info2.htm
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
Nouzui



Зарегистрирован: 07.06.2005
Сообщения: 310

СообщениеДобавлено: 29 Дек 2006, 14:01    Заголовок сообщения: Ответить с цитатой

не дайте умереть дураком..
что это??? :

Код:
#include <stdio.h>
main(t,_,a)
char *a;
{
return!0<t?t<3?main(

  -79,-13,a+main(
    -87,1-_,main(
      -86,0,a+1
      )+a
    )
  ):1,t<_?main(
  t+1,_,a
  ):3,main(-94,-27+t,a)&&t==2?_<13?
main(2,_+1,"%s %d %d\n"):9:16:t<0?t<-72?main(_,t,
"@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l+,/n{n+,/+#n+,/#\
;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l \
q#'+d'K#!/+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# \
){nl]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' \
iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c \
;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')# \
}'+}##(!!/")
:t<-50?_==*a?putchar(31[a]):main(-65,_,a+1):main((*a=='/')+t,_,a+1)
  :0<t?main(2,2,"%s"):*a=='/'||main(0,main(-61,*a,
"!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"),a+1);
}
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
Nouzui



Зарегистрирован: 07.06.2005
Сообщения: 310

СообщениеДобавлено: 29 Дек 2006, 14:15    Заголовок сообщения: Ответить с цитатой

да.. форум вставляет пробелы в конце каждой строки, поэтому, чтобы это скомпилилось, пробелы нужно сначала удалить
компилить как C, не C++
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
Sir Kot



Зарегистрирован: 21.10.2003
Сообщения: 892
Откуда: Korolev City Computer Network

СообщениеДобавлено: 29 Дек 2006, 17:06    Заголовок сообщения: Ответить с цитатой

а ты можешь словами сказать, что это? А то уж больно напомнает хакерский код
_________________
Вы спрашиваете, мы отвечаем. Неофициальная энциклопедия сети Королев.Нет
Вернуться к началу
Посмотреть профиль Отправить личное сообщение MSN Messenger
Nouzui



Зарегистрирован: 07.06.2005
Сообщения: 310

СообщениеДобавлено: 29 Дек 2006, 18:20    Заголовок сообщения: Ответить с цитатой

выводит на экран вот это:
Код:
On the first day of Christmas my true love gave to me
a partridge in a pear tree.

On the second day of Christmas my true love gave to me
two turtle doves
and a partridge in a pear tree.

On the third day of Christmas my true love gave to me
three french hens, two turtle doves
and a partridge in a pear tree.

On the fourth day of Christmas my true love gave to me
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the fifth day of Christmas my true love gave to me
five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the sixth day of Christmas my true love gave to me
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the seventh day of Christmas my true love gave to me
seven swans a-swimming,
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the eigth day of Christmas my true love gave to me
eight maids a-milking, seven swans a-swimming,
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the ninth day of Christmas my true love gave to me
nine ladies dancing, eight maids a-milking, seven swans a-swimming,
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the tenth day of Christmas my true love gave to me
ten lords a-leaping,
nine ladies dancing, eight maids a-milking, seven swans a-swimming,
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the eleventh day of Christmas my true love gave to me
eleven pipers piping, ten lords a-leaping,
nine ladies dancing, eight maids a-milking, seven swans a-swimming,
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the twelfth day of Christmas my true love gave to me
twelve drummers drumming, eleven pipers piping, ten lords a-leaping,
nine ladies dancing, eight maids a-milking, seven swans a-swimming,
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

вообще вещь аццки старая, я ее еще на первом курсе видел
понятно, что это распаковщик, но как конкретно он работает...
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
Dwarflord



Зарегистрирован: 16.05.2004
Сообщения: 383

СообщениеДобавлено: 06 Янв 2007, 11:45    Заголовок сообщения: Ответить с цитатой

Вопрос возник.
Имеем набор натуральных чисел. Числа не повторяются.
Надо посчитать их НОК. Но всё бы ничего, если бы не одно НО. Нужно получить точное число. Пишу в дельфях, там максимальный integer type - это int64.
Так вот этот НОК вполне может не уложиться в int64, а число нужно точное.

P. S.: Про алгоритм Евклида для поиска НОД и формулу НОК через НОД знаю. Это можно не объяснять.
_________________
С уважением, Пётр
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Nouzui



Зарегистрирован: 07.06.2005
Сообщения: 310

СообщениеДобавлено: 06 Янв 2007, 12:42    Заголовок сообщения: Ответить с цитатой

ну поищи какой-нибудь класс для работы с целыми числами больших размерностей
заодно и мне дашь ))
я и сам писал такой когда-то, но там косяки были с делением, да и вообще..
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
Dwarflord



Зарегистрирован: 16.05.2004
Сообщения: 383

СообщениеДобавлено: 06 Янв 2007, 18:01    Заголовок сообщения: Ответить с цитатой

А есть формула, что НОК нескольких чисел можно посчитать как произведение всех делить на произведение НОД каждой пары?

Если есть, то тогда идея есть.
В принципе ведь можно складывать, вычитать, умножать, делить большые числа , как мне кажется.
Просто я не сказал, но сами числа, НОК которых мне надо посчитать, у меня меньше 22500.
В принципе можно изначальна преобразовать их в строки. А затем уже складывать, умножать, делить строки. Сумму строк я вот уже написал. Произведение из суммы тоже понятно как сделать. Осталось только деление.

Только вот меня смущает вопрос - есть ли такая формула?
_________________
С уважением, Пётр
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Nouzui



Зарегистрирован: 07.06.2005
Сообщения: 310

СообщениеДобавлено: 06 Янв 2007, 18:42    Заголовок сообщения: Ответить с цитатой

пытался сейчас сам сообразить, но так и не смог ))
в итоге отыскал в нете:
Код:

m= a;
n= b;
v= a;
u= b;
while(m!=0 && n!=0)
{
      if(m>=n)
      {
            m-= n;
            v+= u;
      }
else
      {
            n-= m;
            u+= v;
      }
}
if(m==0)
{
      NOK= v;
      NOD= n;
}
else
{
      NOK= u;
      NOD= u;
}
NOK/= 2;

и никаких делений

насчет НОК нескольких чисел:
НОК(a, b, c)= НОК(НОК(a, b), c)
итд

ps: а твоя формула в общем случае неверна
например, для трех чисел правильно будет:
НОК(a, b, c)= а*b*c/НОД(a, b)/НОД(a, c)*НОД(НОД(a, b), НОД(a, c))
вроде..
если проще, то:
НОК(a, b, c)= а*b*c/НОД(a, b, c)
но опять же НОД(a, b, c)= НОД(НОД(a, b), c)
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
Nouzui



Зарегистрирован: 07.06.2005
Сообщения: 310

СообщениеДобавлено: 06 Янв 2007, 21:26    Заголовок сообщения: Ответить с цитатой

с формулами я загнался
если подумать, то
НОК(a, b, c)= a*b*c/НОД(a, b)/НОД(b, c)/НОД(a, c)*НОД(a, b, c)
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
Sinister Slaughter



Зарегистрирован: 30.01.2006
Сообщения: 348

СообщениеДобавлено: 28 Авг 2007, 12:34    Заголовок сообщения: Ответить с цитатой

Цитата:

Куайн, квайн (англ. quine) — компьютерная программа (частный случай метапрограммирования), которая выдаёт на выходе точную копию своего собственного исходного текста. Программисты иногда для забавы занимаются разработкой максимально кратких куайнов на различных языках программирования.

Следует заметить, что программы, использующие внешние данные, куайнами не считаются; то есть исключается прочтение текста программы из файла, ввод его с клавиатуры и так далее. Кроме того, не считается куайном «программа», не содержащая вообще никакого кода (вырожденный случай).

Термин получил название от имени американского логика и философа Уилларда Ван Ормана Куайна (англ. Willard Van Orman Quine) (1908—2000), который занимался углубленным изучением косвенного самоупоминания (англ. indirect self-reference).

Разбираясь с программированием на shell, решил попробовать написать:
Код:

#/bin/sh
echo $0 | grep -v \./ | cat $0

Как выяснилось не годиться, из-за того, что идет чтение из файла. Следующее что приходит в голову, вывод предварительного написаного текста, который повторяет исходный код программы, однако, как мне кажется, не является хорошим вариантом. У кого еще есть какие-либо мысли по этому поводу? Если есть уже наработки, то кидайте, язык программирования значения не имеет.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Показать сообщения:   
Начать новую тему   Ответить на тему    Список форумов Форум портала г. Королёва -> Наука и Жизнь Часовой пояс: GMT + 4
На страницу Пред.  1, 2, 3, 4  След.
Страница 3 из 4

 
Перейти:  
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах