| Вопрос: Знакомься: Justbasic | Добавлено: 06.03.08 23:27 |
Автор вопроса:  rulevigor | Web-сайт: www.rulev-igor.narod.ru
|
|
Двадцать лет назад у нас в стране было сто тысяч программистов. Работали на ассемблере, Бейсике, Паскале, Клипере, Си, - писали программы, строили программно-аппаратные комплексы. На каждом предприятии разрабатывали свою «бухгалтерию», свои «кадры». Это была работа столь же приятная, сколь бесполезная, в общем то, удовлетворяли любопытство за казенный счет.
Теперь программные пакеты создают в специализированных фирмах, где есть условия для организации параллельной работы большого количества специалистов. Только так можно в короткие сроки построить серьезный коммерческий продукт, вмещающий в себя тысячи человеко-часов квалифицированного труда. Освободившиеся программисты стали продвинутыми пользователями ПК, работают с готовыми пакетами, с Интернетом. Зная на собственном опыте, насколько увлекательно строить собственную программу, находить оптимальный алгоритм поставленной задачи, искать и исправлять собственные ошибки, я предлагаю всем желающим принять участие в [url=http://www.rulev-igor.narod.ru/theme_16.html]этом[/url] развлекательном проекте. Берется простейший, но достаточно универсальный инструмент, например, Qb40 Microsoft Corporation, его всегда можно бесплатно скачать на портале фирмы, пакет весит всего 560 Kb или же работающий в Windows Justbasic (2.6 Мб). Ставится общая задача. Побеждает тот, чья программа правильнее и быстрей работает. Алгоритм реализации придумывает программист, он же пишет текст и отлаживает программу, текст победителя размещается на сайте. [url] www.rulev-igor.narod.ru/theme_16.html[/url] |
| Ответы | Всего ответов: 31 |
|
Номер ответа: 1 Автор ответа:  Artyom Разработчик Вопросов: 130 Ответов: 6602 |
Профиль | | #1 | Добавлено: 07.03.08 00:51 |
| Предлагаю элементарную задачу - запустить Singularity (http://www.codeplex.com/singularity) на любом компьютере (кроме VPC) | ||
|
Номер ответа: 2 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #2 | Добавлено: 07.03.08 10:56 |
|
Народ, как правило, вяло участвует в подобного рода контестах (что показал, в частности, мой контест KCC3: http://esci.ru/kcc3/kcc3_t.php). В данном случае это применимо куда сильнее, потому что:
- все задачи бояны, особенно первая, которую, по утверждению топикстартера, трудно посчитать комбинаторно, хотя это спокойно делают восьмиклассники. - задачи не формализованы, что отталкивает довольно большое коммьюнити ACM-щиков и топкодеров. - задачи проверяются вручную, что отталкивает остальную часть коммьюнити ACM-щиков и топкодеров - доступен только бейсик, хотя сейчас почти все олимпиадные задачи решаются на C++, C# и Java. В бейсике просто нет ничего похожего на STL, что делает написание алгоритмов на нем до ужаса утомительным. Если есть желание устраивать контесты, лучше связаться со мной и обсудить эту тему 
|
||
|
Номер ответа: 3 Автор ответа:  User UnknownВечный Юзер! ICQ: uu@jabber.cz Вопросов: 120 Ответов: 3302 |
Профиль | | #3 | Добавлено: 07.03.08 11:07 |
|
Мне, например, интереснее исправлять чужие ошибки, чем свои
|
||
|
Номер ответа: 4 Автор ответа: mc-blackICQ: 308-534-060 Вопросов: 20 Ответов: 1860 |
Web-сайт: Профиль | | #4 | Добавлено: 07.03.08 12:23 |
|
Идея в общем-то интересная. Кто желает, тот поучаствует. Я бы написал решение как dll на ассемблере, либо exe (тогда надо самому подсчитывать tickcount). Нужен интерфейс для тестирования, чтобы можно было оценки делать не качественные-визуальные и по внешнему виду кода, а более объективные. Ведь не сравнивать же количество строк кода на basic с количеством инструкций процессора. Короче, всем удачи!
|
||
|
Номер ответа: 5 Автор ответа: rulevigor Вопросов: 1 Ответов: 11 |
Web-сайт: Профиль | | #5 | Добавлено: 07.03.08 16:46 |
|
- все задачи бояны, особенно первая, которую, по утверждению топикстартера, трудно посчитать комбинаторно, хотя это спокойно делают восьмиклассники.
Уважаемый Sharp,Вы, наверное, уже закончили восьмой, интересно было бы увидеть здесь эту самую строчку из сочетаний, перестановок и размеений, дающую верный ответ. - задачи не формализованы, что отталкивает довольно большое коммьюнити ACM-щиков и топкодеров Я как раз и говорю, что главное в работе программиста, - это алгоритм (программиста, а не кодировщика). |
||
|
Номер ответа: 6 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #6 | Добавлено: 07.03.08 19:45 |
|
Комбинаторика на сочетаниях, размещениях и перестановках не оканчивается. В данном случае надо всего лишь посчитать число разбиений чисел от 0 до 27 на 3 неотрицательных целых числа, не больших 9. 8-классник может сделать это так: посчитать число разбиений на 2 (1 2 3 ... 9 10 9 ... 3 2 1), а затем дополнить до тройки сложением 10 таких колонок, сдвинутых по диагонали друг относительно друга. Получится 1,3,6,10,15,21,28,36,45,55,63,69,73,75,75,73,69,63,55,45,36,28,21,15,10,6,3,1. Искомое число это сумма квадратов всех этих чисел. Кстати, оно на твоем сайте посчитано неверно, не 55251, а 55252, 000000 забыл.
http://ru.wikipedia.org/wiki/%D0%A1%D1%87%D0%B0%D1%81%D1%82%D0%BB%D0%B8%D0%B2%D1%8B%D0%B9_%D0%B1%D0%B8%D0%BB%D0%B5%D1%82 Если ты не знаешь, что такое ACM или TopCoder, воспользуйся википедией. Называть обитателей этих святых мест кодерами, не знающими алгоритмы, особенно человеку, не знающему азов математики, так же глупо, как обвинять Солнце в том, что оно не испускает фотоны. |
||
|
Номер ответа: 7 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #7 | Добавлено: 07.03.08 20:26 |
|
Да, а ты не из Воронежа, часом?
|
||
|
Номер ответа: 8 Автор ответа: rulevigorВопросов: 1 Ответов: 11 |
Web-сайт: Профиль | | #8 | Добавлено: 08.03.08 09:21 |
| Отвечу, когда посмотрю в ВИКОПЕДИИ про ФОТОНЫ. | ||
|
Номер ответа: 9 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #9 | Добавлено: 08.03.08 11:00 |
| http://ru.wikipedia.org/wiki/Фотон | ||
|
Номер ответа: 10 Автор ответа: rulevigorВопросов: 1 Ответов: 11 |
Web-сайт: Профиль | | #10 | Добавлено: 08.03.08 19:45 |
|
Ваша АСМ напоминает мне про-советские соревнования дояров на звание «лучший по профессии».
Если серьезно, то в АСМ секции участвуют профессионалы и, хоть она и некоммерческая, цели, которые преследуются участниками, известны: поиск лучших предложений по собственному трудоустройству. То, что предлагается здесь – это интеллектуальное развлечение и досуг. И предназначено это не для профи-программистов, а для школьников и студентов, домохозяек и пенсионеров, другая ниша, понимаете ли. Что касаемо выбора Бейсика, то аргументы такие: [Бейсик для такого развлекательно-познавательного проекта хорош тем, что с его основами знакомы многие, он имеет несложные операторы, терпим к некомпетентному обращению, его оболочки реализуют подробный хелп и контекстные подсказки. Поэтому новичок может сразу начинать работу и получать конкретный результат, самообучение идет быстро и без негативных эмоций. Бейсик непотопляем, он вбирает в себя все лучшее из других языков, на нем можно написать и примитивную программу и хорошо структурированный модуль, его текст транслируется в exe-файл, он оперирует с хорошей графикой, с ним работают с помощью современной Windows-оболочки. А Ваше решение первого «бояна» ровно соответствует второму варианту, приведенному мною на сайте, и комбинаторика здесь вовсе не причем. Использование STL-библиотек приводит к более медленно работающему варианту странслированного exe-модуля, а, следовательно к проигрышу по оговоренным условиям (даже при одинаково эффективных алгоритмах. |
||
|
Номер ответа: 11 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #11 | Добавлено: 08.03.08 21:16 |
|
ACM, прямо так скажем, не моя, а очень даже международная организация.
Что ты имеешь против советских соревнований на звание лучшей доярки? В ACM ICPC участвуют студенты, которые ставят перед собой цель применить на практике знания алгоритмов и математики. С трудоустройством это связано слабо, хотя очевиден тот факт, что успешно выступающие на ACM люди в последующем не имеют никаких проблем с трудоустройством. Собственно и я, и большая часть знакомых мне олимпиадников как раз и рассматривают ACM и TopCoder в качестве замечательного интеллектуального развлечения, способа провести время с интересными людьми, темы для общения между единомышленниками. А профессиональные программисты редко участвуют в TopCoder (в ACM вообще не могут). А если и участвуют, то в чем-то менее спортивном, к примеру, ICFPC. Аргументы в пользу Basic несколько смехотворны, а статистика очевидно высосана из пальца. На Basic сейчас не пишут даже школьники. Так что это ни в коей мере не замануха, а очень даже отталкивающий пункт. Посмотрите хотя бы на KCC3: там разрешено использовать 11 языков. В ICFPC и ProjectEuler вообще никак не ограничен инструментарий. На TopCoder и ACM ICPC, при очень суровых требованиях к надежности, безопасности и демократичности соревнований, и то: разрешено 3-4 языка. Число разбиений это самая натуральная комбинаторика, в частности, оно выражается через число сочетаний. Из того, что это число можно посчитать на компьютере, не следует, что комбинаторика ни при чем. Число сочетаний тоже можно. Использование STL приводит к ускорению работы программы в подавляющем большинстве случаев, даже если предположить, что программист изобретает качественные велосипеды, отказываясь от него. Это связано с тем, что на отладку, профайлинг и рефакторинг STL потрачено столько человеко-часов, сколько не могут позволить себе тратить даже очень крупные компании (смогли пока только MS, EA, SGI и некоторые другие). В мире существует не так много реализаций STL, и все они оптимизированы намного лучше, чем самые гениальные велосипеды. Мне уже посылать учить матчасть, или необходимость этого и так уже понятна? |
||
|
Номер ответа: 12 Автор ответа: rulevigorВопросов: 1 Ответов: 11 |
Web-сайт: Профиль | | #12 | Добавлено: 08.03.08 22:19 |
| Ну что ж, решите второй "боян" на чем угодно, (результат известен) и выдайте exe-модуль, а я пришлю свой. Сравним быстродействие. | ||
|
Номер ответа: 13 Автор ответа: ArtyomРазработчик Вопросов: 130 Ответов: 6602 |
Профиль | | #13 | Добавлено: 08.03.08 22:36 |
|
... а я пришлю свой
Можешь не утруждать себя, все равно ни один адекватный участник форума его не запустит
|
||
|
Номер ответа: 14 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #14 | Добавлено: 09.03.08 13:38 |
|
Да пожалуйста:
#include <windows.h>
#pragma comment (lib, "winmm.lib" 
#include <iostream> #include <vector> using namespace std; int main(){ DWORD t1 = timeGetTime(); int cost[] = {1, 2, 3, 5, 10, 15, 20, 50}; vector<int> a(101, 1), b(101, 1); for(int i = 1; i < 8; i++){ int u = cost[i]; for(int j = u; j <= 100; j++){ int ccost = j - u; while(ccost >= 0){ b[j] += a[ccost]; ccost -= u; } } a = b; } DWORD t2 = timeGetTime(); cout << a[100] << endl; cout << (t2 - t1) << "ms" << endl; return 0; } Компилировалось в VC++ 2005, конфигурация, разумеется, Release. Время исполнения 100000 прогонов 3357 мсек, т.е. время решения 33.5 микросекунды. Процессор: Celeron-1.7 GHz, следовательно, около 60000 тактов. Очень любопытно будет посмотреть на решение, хотя бы на порядок быстрее тормознутого STL. Присылай исходники, в чем их компилировать, и сравним. |
||
|
Номер ответа: 15 Автор ответа: rulevigorВопросов: 1 Ответов: 11 |
Web-сайт: Профиль | | #15 | Добавлено: 09.03.08 15:40 |
|
Я не понимаю Вашего исходника и поэтому мне уверен, что Вами найдены все 66948 вариантов расклада.
Присылаю свой исходник DECLARE SUB NullSumma (i  'декларации и объявления
DECLARE SUB Analiz (i
DECLARE SUB Vybor (i
DECLARE SUB Otobrazenie (i%, j) DECLARE SUB Dobavka (i%, t
DIM SHARED A%(7, 1) COMMON SHARED Sum% CLS SCREEN 11 ' больш. экран OPEN "o", #1, "protokol.txt" 'открыть протокол PRINT #1, "Possible variants of a set" PRINT #1, "Face values "; DATA 1,2,3,5,10,15,20,50 ' задать состав набора FOR k = 0 TO 7 READ A%(k, 0): PRINT #1, A%(k, 0); " "; NEXT: PRINT #1, : PRINT #1, WHILE f% = 0 ' цикл перебора вариантов CALL Analiz(i ' анализ предыдущей комбинации
CALL NullSumma(i ' вычисл. начальной суммы
FOR k = 1 TO 100 ' цикл построения очередной комбинации A%(i%, 1) = k CALL Dobavka(i%, t ' работа с суммой
IF t% = 1 THEN j = j + 1: CALL Otobrazenie(i%, j) IF t% > 0 THEN k = 100 NEXT IF A%(0, 1) = 100 THEN f% = 1 ' условие выхода с главного цикла 'IF j = 210 THEN f% = 1 ' отлад. выход WEND PRINT "In total it is found variants: . . . . . . . . "; j PRINT #1, "In total it is found variants: . . . . . . . . "; j END SUB Analiz (i ' разбор пред. набора, поиск рабочего звена
A%(0, 1) = 0: i% = 7 ' левое звено игнорируется FOR k = 0 TO 7 ' ненулевое звено IF A%(k, 1) > 0 THEN A%(k, 1) = A%(k, 1) - 1: i% = k - 1: k = 7 NEXT END SUB SUB Dobavka (i%, t ' наращивание суммы, в случае перепол-
t% = 0: Sum% = Sum% + A%(i%, 0) ' -нения возврат IF Sum% > 100 THEN Sum% = Sum% - A%(i%, 0): t% = 2 IF Sum% = 100 THEN t% = 1 END SUB SUB NullSumma (i ' подсчет значения, с которого начина-
Sum% = 0 ' -ется анализ нового набора FOR k = 0 TO 7 Sum% = Sum% + A%(k, 1) * A%(k, 0) NEXT END SUB SUB Otobrazenie (i%, j) STATIC ' внутр. перем. сохр. в процедуре m = m + 1 ' занесение в протокол результатов IF m = 100 THEN PRINT #1, "N"; j; " . . . "; PRINT "N"; j; " . . . " m = 0 ELSE PRINT #1, " . . . . . "; END IF FOR k = 0 TO 7 PRINT #1, A%(k, 1); " "; NEXT PRINT #1, END SUB Здесь формируется txt-протокол вариантов. Если хотите, я очищу программу от "излишеств" иприкреплю exe-файл к E-mail. |
||