|
занятие 8_11_07 [программирование]
| |
| vorl | Дата: Четверг, 08.11.2007, 21:48 | Сообщение # 1 |
 Рядовой
Группа: 11
Сообщений: 16
Статус: Offline
| Quote сумма всех попарных произведений элементов последовательности
сумму 1*2 + 1*3 + 1*4 + 2*3 + 2*4 + 3*4 можно представить как:
(1 + 2 + 3)*4 + (1 + 2)*3 + 1*2 = 1*2 + (1 + 2)*3 + (1 + 2 + 3)*4
легко догадаться, что для последовательности получим
x1*x2 + (x1+x2)*x3 + (x1+x2+x3)*x4 + ... + (x1+x2+...+x(n-1))*xn + ...
т.е. чтобы вычислить сумму попарных произведений элементов последовательности нежны: сумму элементов и сама сумма попарных произведений
вот код
Code
begin
sum2 = nil
sum1 = readline.to_f
while true
x2 = readline.to_f
if !sum2.nil?
sum2 += sum1*x2
else
sum2 = sum1*x2
end
sum1 += x2
end
rescue EOFError
puts sum2
end
skype: vorl13
(\(\
(>'.')
(~(")(")
|
| |
| |
| ldo2 | Дата: Суббота, 10.11.2007, 16:39 | Сообщение # 2 |
 Сержант
Группа: 11
Сообщений: 88
Статус: Offline
| Quote ДЗ найти длину наибольшей возрастающей подпоследовательности
Как это понимать? Что такое подпоследовательность(Тинякова не цитировать)?
И что такое наибольшая? PS скрипт для наибольшей по длине,
такое не зачтут тк здесь запоминается вся подпоследовательность, и для каждого эл-та длина цепочки...
(возможно здесь есть ошибки)
Code
def binar_search(ar, el)
i, j = 0,ar.size-1
while i+1 != j
k = (i+j)/2
ar[k] <= el ? i=k : j=k
end
return i
end
begin
elemts=[readline.to_f]
nums=[1]
while 13
elem = readline.to_f
if elem < elemts[0]
elemts.unshift(elem)
nums.unshift(1)
next
elsif elem > elemts[-1]
elemts << elem
nums << 1
i = -1
elsif elem == elemts[-1]
i = -1
else
i = binar_search(elemts, elem)
if elemts[i]!=elem
elemts.insert(i+1, elem)
nums.insert(i+1, 1)
i+=1
end
end
nums[i]=nums[0 ... i].max+1
end
rescue EOFError
puts nums.max
end
Основная проблема современности - коммуникационная.
jabber: ldo2@jabber.ru
skype: ldo1
|
| |
| |
| y0ma | Дата: Суббота, 10.11.2007, 16:49 | Сообщение # 3 |
 Рядовой
Группа: 11
Сообщений: 14
Статус: Offline
| ldo2, скорее всего имелась ввиду наибольшая по длине вырезка.
У меня вопросы в другом:
- {1} - возрастающая подпоследовательность?
- {1,2,3,3,3,4,5} - возрастающая?Добавлено (10.11.2007, 16:49)
---------------------------------------------
А с другой стороны, в условии ничего конкретного не сказано, поэтому я могу понять это так, как мне захочется! =))
Я в контакте, skype: y0ma97
|
| |
| |
| ldo2 | Дата: Суббота, 10.11.2007, 16:54 | Сообщение # 4 |
|
Сержант
Группа: 11
Сообщений: 88
Статус: Offline
| y0ma, я полагаю, что {1} - возрастающая , а {1,2,3,3,3,4,5} -не является возрастающей, хотя является не убывающей
Основная проблема современности - коммуникационная.
jabber: ldo2@jabber.ru
skype: ldo1
|
| |
| |
| Xaron1 | Дата: Суббота, 10.11.2007, 21:31 | Сообщение # 5 |
|
Группа: Удаленные
| {1} - скорее и возрастающая, и убывающая, т.е. константная.
{1,2,3,3,3,4,5} - согласен, неубывающая.
Возрастающая, это когда для любой пары n1 и n2, из того, что n2>n1 следует, что элемент с номером n2 строго больше эелемента с номером n1. Думаю, правильное определение.
Подпоследовательность - любое колличество подряд идущих элементов исходной последовательности, думаю так.
|
| |
| |
| Chuvaver | Дата: Суббота, 10.11.2007, 21:43 | Сообщение # 6 |
 Сержант
Группа: 11
Сообщений: 54
Статус: Offline
| Моя версия.
Тока неручаюсь за правильность! Если есть идеи, как ее модернизировать пишите! begin
a = readline.to_f
s=1
m=0
while true
x = readline.to_f
if a<x then s+=1 else
if s>=m then m=s; s=0 end end
end
rescue EOFError
puts m
end
Собираю монеты! Приму в дар, все что не жалко!!!
|
| |
| |
| Xaron1 | Дата: Суббота, 10.11.2007, 22:01 | Сообщение # 7 |
|
Группа: Удаленные
| begin
s=0
m=0
while true
x = readline.to_f
if a.nil? || a<x
s+=1
else
m=s if s>m
s=0
end
a=x
end
rescue EOFError
m=s if s>m
puts m
endДобавлено (10.11.2007, 22:01)
---------------------------------------------
Вариант не последний, писал на коленке, да еще и при отсылке все отступы потерлись, поэтому программа имеет плохое форматирование.
|
| |
| |
| ldo2 | Дата: Воскресенье, 11.11.2007, 11:30 | Сообщение # 8 |
|
Сержант
Группа: 11
Сообщений: 88
Статус: Offline
| Что делают эти программы?
Chuvaver, она даже почти не работает(возможно там просто где-то что-то не присваивается) завалилась на самом простом случае
1 2 3 4 она выдала "0".
Xaron, программа (ошибка, надо проинициализировать "а" nil'ом "undefined local variable or method `a' for main:Object (NameError)")
прошла тривиальный тест, но засыпалась на остальных, хотя они удовлетворяют определению подпоследовательности, приведенному выше: 2, 1, 2, 3, 4 - 3 вместо 4; 1, 2, 10, 5, 8, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7 - 7 вместо 8. Думаем дальше...
Основная проблема современности - коммуникационная.
jabber: ldo2@jabber.ru
skype: ldo1
|
| |
| |
| Chuvaver | Дата: Воскресенье, 11.11.2007, 12:52 | Сообщение # 9 |
|
Сержант
Группа: 11
Сообщений: 54
Статус: Offline
| ldo2, Xaron, поправил - теперь вроде правильно!
ldo2, проверь на тестах. Если можешь, выложи их... begin
a = readline.to_f
s=1
m=0
while true
x = readline.to_f
if a<x then s+=1 else
if s>=m then m=s; s=0 end end
end
rescue EOFError
m=s if s>m
if m==0 then puts s else puts m end
end
Собираю монеты! Приму в дар, все что не жалко!!!
|
| |
| |
| DestroFun | Дата: Воскресенье, 11.11.2007, 14:10 | Сообщение # 10 |
 Рядовой
Группа: 11
Сообщений: 11
Статус: Offline
| Chuvaver, не знаю, будет ли пустая последовательность в тестах Рогановой, но твоя прога в этом случае не работает.
Кроме того, она считает неубывающие, а не возрастающие последовательности (последующий элемент строго больше предыдущего). Т.е. результатом для 1 2 2 2 будет 2, а не 4. Мой вариант:
###
ans,cur,prev=0,1,nil
begin
while true
x=readline.to_f
if !prev.nil? && x>prev
cur+=1
ans=cur if ans<cur
else
cur=1
end
prev=x
end
rescue EOFError
puts ans
end
###
|
| |
| |
| vorl | Дата: Воскресенье, 11.11.2007, 14:24 | Сообщение # 11 |
|
Рядовой
Группа: 11
Сообщений: 16
Статус: Offline
| есди полагать, что {1} - возрастающая, и |{1}| = 1,
и {a_n} возрастает, если \All n1,n2 (n2 > n1 => a_n2 > a_n1)
Code
begin
x1 = readline.to_f
len = 1; max_len = 0
while true
x2 = readline.to_f
if x2 > x1
len += 1
x1 = x2
max_len = len if len > max_len
else
max_len = len if len > max_len
len = 1
x1 = x2
end
end
rescue EOFError
puts max_len
end
skype: vorl13
(\(\
(>'.')
(~(")(")
|
| |
| |
| Chuvaver | Дата: Воскресенье, 11.11.2007, 15:06 | Сообщение # 12 |
|
Сержант
Группа: 11
Сообщений: 54
Статус: Offline
| DestroFun, понял свою ошибку! Спасибо, что натолкнул на мысль!
Собираю монеты! Приму в дар, все что не жалко!!!
|
| |
| |
| ldo2 | Дата: Воскресенье, 11.11.2007, 16:14 | Сообщение # 13 |
|
Сержант
Группа: 11
Сообщений: 88
Статус: Offline
| vorl, программа работает не верно, если считать что
\forall n1,n2 (n2 > n1 => a_n2 > a_n1)
тк например для 1, 2, 10, 5, 8, 6, 7 правильным ответом будет 5, а не 3Добавлено (11.11.2007, 16:14)
---------------------------------------------
и для {1}, она не выдает 1!!!
Основная проблема современности - коммуникационная.
jabber: ldo2@jabber.ru
skype: ldo1
|
| |
| |
| vorl | Дата: Воскресенье, 11.11.2007, 17:07 | Сообщение # 14 |
|
Рядовой
Группа: 11
Сообщений: 16
Статус: Offline
| ldo2, Quote vorl, программа работает не верно, если считать что
\forall n1,n2 (n2 > n1 => a_n2 > a_n1)
тк например для 1, 2, 10, 5, 8, 6, 7 правильным ответом будет 5, а не 3
там просто надо было написать \All n1,n2 (n2-n1 =1 =>....)
Quote и для {1}, она не выдает 1!!!
просто руки пишут не то что думает голова 
в проге тот случай когда |{1}| = 0, но при этом для {1,1,1} она выдаст 1,
поутомы надо заманить до while
Code
len = 1; max_len = 0
на
Code
len = 1; max_len = 1
skype: vorl13
(\(\
(>'.')
(~(")(")
|
| |
| |
| sma39 | Дата: Воскресенье, 11.11.2007, 17:27 | Сообщение # 15 |
 Лейтенант
Группа: 61
Сообщений: 114
Статус: Offline
| Че-то я так и не понял что для чего должно выдаваться.
Для
1){1} 0 или 1?
2){2,2,2} 0, 1 или 3?
3){3, 4, 12, 7, 11, 8, 9} здесь ответ должен быть 3?
4){} а здесь чего?
|
| |
| |
| Xaron1 | Дата: Воскресенье, 11.11.2007, 17:55 | Сообщение # 16 |
|
Группа: Удаленные
| sma39, по моим представлениям: 1) 1, так как {1} - наидлиннейшая возрастающая;
2) 1, так как {2} - наидлиннейшая возрастающая;
3) 3, так как {3,4,12} - наидлиннейшая возрастающая;
4) а здесь неопределена, так как {} - не последовательность, так как мы не может указать таких N1, N2, чтобы все натуральные n, принадлежащие [N1,N2) были номерами предложенной цепочки.
|
| |
| |
| Chuvaver | Дата: Воскресенье, 11.11.2007, 17:56 | Сообщение # 17 |
|
Сержант
Группа: 11
Сообщений: 54
Статус: Offline
| Объединение двух подпоследовательностей есть новая подпоследовательность?
Собираю монеты! Приму в дар, все что не жалко!!!
|
| |
| |
| Xaron1 | Дата: Воскресенье, 11.11.2007, 18:21 | Сообщение # 18 |
|
Группа: Удаленные
| Сорри, ребята, а что такое подпоследовательность? Вот, читаю на wiki, что Quote Подпоследовательность можно получить из некоторой конечной последовательности, если удалить из последней некоторое множество её элементов (возможно пустое). Добавлено (11.11.2007, 18:21)
---------------------------------------------
Chuvaver, Quote (Chuvaver) Объединение двух подпоследовательностей есть новая подпоследовательность?
Не всегда. Последовательность {12,45,2,56,4,78}. В ней есть подпоследовательности {12,2} и {45,56}. Объединяем: {12,2,45,56} - но это уже не подпоследовательность
|
| |
| |
| sma39 | Дата: Воскресенье, 11.11.2007, 18:24 | Сообщение # 19 |
|
Лейтенант
Группа: 61
Сообщений: 114
Статус: Offline
| Вот и у меня сомнения по этому поводу. Поэтому и дал такую последовательность для расмотрения.
Quote (Xaron) а здесь неопределена, так как {} - не последовательность, так как мы не может указать таких N1, N2, чтобы все натуральные n, принадлежащие [N1,N2) были номерами предложенной цепочки.
наверное нужно nil выдавать. Или может быть 0?
|
| |
| |
| Xaron1 | Дата: Воскресенье, 11.11.2007, 18:45 | Сообщение # 20 |
|
Группа: Удаленные
| sma39, а мне кажется тут все равно, так как раз функция не определена, то и результат может быть какой угодно. Хотя 0 - ответ приемлемый мне кажется. Какая длинна? 0, т.е. нет длинны. Добавлено (11.11.2007, 18:45)
---------------------------------------------
А могла вообще роганова под подпоследовательностью иметь ввиду именно вырезку, как мы ранее предполагали? А то меня терзают смутные сомнения о решении усложнившейся задачи...
|
| |
| |
| Paravinci | Дата: Понедельник, 12.11.2007, 19:14 | Сообщение # 21 |
|
Группа: Удаленные
| Сори что без кода  Единственное решение, которое приходит мне в голову - это хранить в хеше максимальную длину подпоследовательности, оканчивающуюся на данное число. (т.е. пусть в начале size = Hash.new(0), а в цикле size[x] - максимальная длина возрастающей подпоследовательности, заканчивающаяся на x).
После получения нового числа я прохожу по всему хешу и нахожу наибольшую подпоследовательность к которой можно приписать x, так чтобы она осталась возрастающей. Дальше нужно просто сохранить длину новой подпоследовательности в хеше (+ незабыть о нескольких проверках), но до этого проще догадаться, чем описывать.
Программа написанная таким образом корректно обрабатывает все тесты, которые здесь приводились. Плюс есть идейка об одной оптимизации, но я её не производил и описывать не буду %).
|
| |
| |
| Xaron1 | Дата: Вторник, 13.11.2007, 17:22 | Сообщение # 22 |
|
Группа: Удаленные
| Paravinci, никто не говорит, что код именно для подпоследовательностей написать нереально. Ммм, просто Роганова дала ясно понять, что в заданиях этого занятия хеши и массивы неприменимы в виду потенциальной бесконечности последовательностей, а значит различных чисел, из которых они могут состоять. Лично я буду отправлять Рогановой вариант кода про вырезки, но, как всегда, не настаиваю на своей правоте.
|
| |
| |
| kmeaw | Дата: Вторник, 13.11.2007, 17:58 | Сообщение # 23 |
 Рядовой
Группа: Проверенные
Сообщений: 35
Статус: Offline
| Задача про подпоследовательности довольно просто решается, если ответить на вопрос: какие числа можно дописать к возрастающей последовательности, чтобы она осталась возрастающей последовательностью?
--
kmeaw aka bdd1
|
| |
| |
| Paravinci | Дата: Вторник, 13.11.2007, 19:04 | Сообщение # 24 |
|
Группа: Удаленные
| Xaron, я тоже думал на эту тему, но уже отправил с хешами.
В моей программе сохраняется только неповторяющиеся элементы. И хотя их количество может достигать бесконечности это всё-же не все элементы последовательности.
В качестве возможной оптимизации по памяти могу предложить на каждой итерации проходиться по хешу и выкидывать оттуда данные (x, size[x]) о таких подпоследовательностях, которые оканчиваются на число большее данного (current_x) и для которых длина максимальной подпоследовательности (size[current_x]) меньше, чем длина максимальной подпоследовательности, оканчивающееся на текущее число, т.е. x > current_x && size[x] < size[current_x].Добавлено (13.11.2007, 19:04)
---------------------------------------------
Дополнение 1: конечно, несмотря на такую оптимизацию все-равно можно подобрать такую последовательность, что хеш всё-равно будет содержать бесконечно много элементов. Так что это не выход
|
| |
| |
| Xaron1 | Дата: Четверг, 15.11.2007, 01:58 | Сообщение # 25 |
|
Группа: Удаленные
| В задачах ко второму коллоквиуму у Роганова есть одна, похожая на домашку. Принципиальных отличий только две: 1) ищется не максимальная, а средняя длинна; 2) речь идет о связанной подпоследовательности, которыю мы все здесь дружно называли вырезкой. Так что и у Ронановой, скорее всего, имеется ввиду именно связанная подпоследовательность, просто, как это у них часто бывает, сформулированно не совсем корректно.
|
| |
| |
|
