2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней. На страницу Пред.  1 ... 9, 10, 11, 12, 13  След.
 
 Re: Программирование для неудачников
Сообщение05.03.2013, 12:32 


26/08/11
2108
arseniiv в сообщении #690157 писал(а):
Задача с инверсиями задела. Ничего лучше следующего не придумал:
Попробовал с массив типа бинарное дерево с дополнительной переменной, хранящая число елементов в левой ветви (плюс один).
Время работы функции (при 50000 елементов) - 15-20 миллисекунд на Visual Basic :roll: (правда, чтение не из файла, а генерация случайных чисел в тело функции)
Число инверсий - около 625 млн. Код:
код: [ скачать ] [ спрятать ]
Используется синтаксис Visual Basic
Const N = 50000
Private Type BinaryTree
 Value As Long
 Left As Long
 Right As Long
 LeftCount As Long
End Type
Dim M(1 To N) As BinaryTree

Function Inversions() As Long
Dim Result As Long, I As Long, TPoint As Long
Result = 0
M(1).Value = Int(Rnd * 1000000)
M(1).Left = 0
M(1).Right = 0
M(1).LeftCount = 1

For I = 2 To N
 M(I).Value = Int(Rnd * 1000000)
 M(I).Left = 0
 M(I).Right = 0
 M(I).LeftCount = 1
 TPoint = 1
 While TPoint <> 0
  If M(I).Value < M(TPoint).Value Then
   Result = Result + M(TPoint).LeftCount
   If M(TPoint).Right = 0 Then
    M(TPoint).Right = I
    TPoint = 0
   Else
    TPoint = M(TPoint).Right
   End If
  Else
   M(TPoint).LeftCount = M(TPoint).LeftCount + 1
   If M(TPoint).Left = 0 Then
    M(TPoint).Left = I
    TPoint = 0
   Else
    TPoint = M(TPoint).Left
   End If
  End If
 Wend
Next I
Inversions = Result
End Function
На C конечно все улучшится.
Теоретически возможно переполнение для результата.

 Профиль  
                  
 
 Re: Программирование для неудачников
Сообщение05.03.2013, 19:28 


26/08/11
2108
Shadow в сообщении #691385 писал(а):
Число инверсий - около 625 млн
Ну да, неудивительно $\dfrac{C_{50000}^2}{2}$

 Профиль  
                  
 
 Re: Программирование для неудачников
Сообщение05.03.2013, 19:34 


22/01/11
309
Zealint в сообщении #690926 писал(а):
Вот кто остаётся в конце, тот как раз и разбирается, плюс с ними остаётся пара технарей, которые умеют только кодировать, но пошустрее стучат по клавиатуре.
Математики, как правило, не приходят из неоткуда, обычно они же ещё раньше начали посещать математические кружки, а потом пришли к нам.


Я имею в виду из тех 250-ти.

 Профиль  
                  
 
 Re: Программирование для неудачников
Сообщение06.03.2013, 10:24 


26/01/10
959
Esp_ в сообщении #691538 писал(а):
Я имею в виду из тех 250-ти.

Я тоже это имею ввиду.

 Профиль  
                  
 
 Re: Программирование для неудачников
Сообщение07.03.2013, 23:35 


05/09/12
2587
Xaositect в сообщении #690166 писал(а):
Для перестановки можно $O(n)$ через разбиение на циклы.
Не могли бы черкнуть несколько слов - идею? Почитал интернет, получил представление как разбить перестановку на циклы (только имея её полностью записанную в массиве, а не поступающую ещё по входному потоку), каждый цикл можно представить как последовательность транспозиций, но не додумался как из этого можно определить количество инверсий.

 Профиль  
                  
 
 Re: Программирование для неудачников
Сообщение09.03.2013, 13:20 


30/11/10
80
Shadow в сообщении #691385 писал(а):
arseniiv в сообщении #690157 писал(а):
Задача с инверсиями задела. Ничего лучше следующего не придумал:
Попробовал с массив типа бинарное дерево с дополнительной переменной, хранящая число елементов в левой ветви (плюс один).
Время работы функции (при 50000 елементов) - 15-20 миллисекунд на Visual Basic :roll: (правда, чтение не из файла, а генерация случайных чисел в тело функции)

По условию числа в последовательности не должны повторятся, а у вас могут, вы просто генерируете
их случайно, а возможный повтор не отслеживаете.

 Профиль  
                  
 
 Re: Программирование для неудачников
Сообщение09.03.2013, 13:43 
Заслуженный участник
Аватара пользователя


06/10/08
6422
_Ivana в сообщении #692423 писал(а):
Xaositect в сообщении #690166 писал(а):
Для перестановки можно $O(n)$ через разбиение на циклы.
Не могли бы черкнуть несколько слов - идею? Почитал интернет, получил представление как разбить перестановку на циклы (только имея её полностью записанную в массиве, а не поступающую ещё по входному потоку), каждый цикл можно представить как последовательность транспозиций, но не додумался как из этого можно определить количество инверсий.
Вспомнил, что я тогда придумал и понял, что ошибся. Там у меня внутри незаметно вкралась сортировка.

 Профиль  
                  
 
 Re: Программирование для неудачников
Сообщение09.03.2013, 14:08 


26/08/11
2108
DVN в сообщении #693021 писал(а):
По условию числа в последовательности не должны повторятся, а у вас могут, вы просто генерируетеих случайно, а возможный повтор не отслеживаете.
Ну значит алгоритм решает более общую задачу - когда числа могут повторятся - одинаковые числа не считаются в инверсии и все.
Входные данные не я должен генерировать - их нужно читать от файл, я просто тестовал скорость -вполне удовлетворительна.

 Профиль  
                  
 
 Re: Программирование для неудачников
Сообщение09.03.2013, 22:41 


05/09/12
2587
Попробовал погонять код Shadow, впечатляет. Насколько я понял, мы можем заранее не знать число элементов, в любой момент можем остановиться и результат будет верный. Плюс не обязательно условие различности элементов. И при всем этом на каждый входящий новый элемент последовательности выполняется всего около 20+- раз внутренний цикл пробега по дереву, причем это число фактически стационарно и не растет с течением входных данных, во всяком случае, при случайных данных (может можно специально сделать ряд когда оно будет линейно расти, например обратный порядок). Массив с дополнительными параметрами конечно придется запоминать весь.
UPD да, при обратном порядке входных элементов размер внутреннего цикла растет линейно на 1-цу с каждым входным элементом. При 50000 я не дождался конца работы программы...

И зачем в условии ограничения на различность входных данных и сразу дается размер массива?....

 Профиль  
                  
 
 Re: Программирование для неудачников
Сообщение10.03.2013, 10:31 


26/08/11
2108
_Ivana в сообщении #693406 писал(а):
При 50000 я не дождался конца работы программы...

Нууууууу и процессор у Вас....Вы exe откомпилировали? При таких условий работает 4-6 секунд.

 Профиль  
                  
 
 Re: Программирование для неудачников
Сообщение10.03.2013, 15:31 


05/09/12
2587
Нет, я в Экселевский макрос вставлял код и исполнял его :-) Когда ставил Вижуал Студию, то снял все не требующиеся мне опции, в т.ч. и поддержку VBasic, поэтому затрудняюсь получить exe файл. Хорошо ещё код на VBasic есть где протестировать, с Паскалем в этом смысле хуже, не говоря уже о Haskell и Prolog.

UPD здесь http://liveworkspace.org/ тоже ни Бэйсика на Паскаля, зато Хаскелл с Лиспом есть :-)

 Профиль  
                  
 
 Re: Программирование для неудачников
Сообщение11.03.2013, 06:41 


28/12/05
160
Ktina в сообщении #683443 писал(а):
Итак, мой вопрос в следующем. Я бы хотела предпринять вторую попытку научиться программировать. Единственная возможность для меня сделать это -- только через интернет. Но в Сети полно материала и я теряюсь -- а вдруг не пойдёт, как в прошлый раз?
Хотелось бы найти что-нибудь, ну совсем уж для полных чайников, причём чтобы имелась возможность практиковаться прямо на месте, то есть, чтобы была среда, в которой можно было бы сразу начинать писать какие-нибудь программы.

Буду очень благодарна за помощь!


http://vb2010.ru/

 Профиль  
                  
 
 Re: Программирование для неудачников
Сообщение11.03.2013, 10:16 
Заслуженный участник


27/04/09
28128

(Оффтоп)

Ну и терминология у них там. «Визуальные объекты»… Как будто они чем-то разительно отличаются от остальных, а в рассмотрении используются сплошь одни отличающие их от других объектов свойства. Да и, коли называть, есть же «компоненты», «элементы управления» и пр..

 Профиль  
                  
 
 Re: Программирование для неудачников
Сообщение22.04.2013, 13:48 
Аватара пользователя


02/03/08
178
Netherlands
Ktin-ушка, попробуйте также обратить внимание на mathcad (у меня был потом MatLab, потом Builder C++). Он очень простенький и наглядный и лагает :D
Придётся конечно научиться ставить пиратское ПО. Да и вообще, сначала с компьютером в целом надо хорошенько познакомиться. Такова бесплатная халява...

 Профиль  
                  
 
 Re: Программирование для неудачников
Сообщение22.04.2013, 14:00 
Заслуженный участник


11/05/08
32166
Dimoniada в сообщении #714042 писал(а):
попробуйте также обратить внимание на mathcad

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 193 ]  На страницу Пред.  1 ... 9, 10, 11, 12, 13  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group