[Любой язык] Реализация интересной задачи

enochka1145

Чего бы хотелось мне, так это посмотреть, как различные задачи (а не только "Hello, world!") реализуются на различных языках программирования. Если есть желание показать различные языки в деле, предлагайте свои задачи. Под этим ником - - я буду всячески нахваливать именно Java. Так что если у кого есть желание поопускать Java или Java-программистов - вам особое приглашение.

garikus

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


MODULE Gcds;



	(* Модуль нахождения наибольших общих делителей *)



	IMPORT Log := StdLog;



	(* Алгоритм Евклида *)

	PROCEDURE Euclid* (x, y: INTEGER): INTEGER;

	BEGIN

		ASSERT(x > 0); ASSERT(y > 0);

		WHILE x # y DO

			IF x > y THEN x := x - y ELSE y := y - x END

		END;

		RETURN x

	END Euclid;



	PROCEDURE Test* (x, y: INTEGER);

	BEGIN

		Log.Int(Euclid(x, y; Log.Ln

	END Test;



END Gcds.

"Gcds.Test(45, 120)"
15

shlyumper

Алгоритм эвклида. Тот же самый. Ocaml.


# let rec gcd n m = if n = 0 then m else if n >= m then gcd (n - m) m else gcd m n ;;

val gcd : int -> int -> int = <fun>

# gcd 45 120 ;;

- : int = 15

rosali

На самом деле if n >= m не нужно.
Haskell: 


gcd 0 a = a

gcd a b = gcd b (a `mod` b)
PS У тебя нет ASSERT(x>0) и IO тоже нет

rosali

Классическим членомерством для Haskell-я является qsort:
 

qsort [] = []

qsort (x:xs) = qsort [x' | x'<-xs, x'<x] ++ [x] ++ qsort [x' | x'<-xs, x'>=x]

bleyman

хм.
Красивый язык.
Надо взботнуть!

a10063

я тоже заинтересовался
а свободная реализация компилятора под свободную ос есть?

rosali

а свободная реализация компилятора под свободную ос есть
Из популярных реализаций знаю hugs и ghc. Я правда обычно интерпретатором пользовался , но компиляторы там тоже есть.

Ivan8209



: gcd  begin ?dup while 2dup - abs -rot min repeat ;

45 120 gcd . 15  ok

Короче.
Даже если защищаться от отрицательных значений:


: gcd  begin ?dup while over abs over abs - abs -rot min repeat ;

---
VARIABLE 1

Hastya

COMPARISON ?> IF DUP - ELSE SWAP DUP - THEN;
BEGIN COMPARISON ?= UNTIL;
EMIT;
язык Форт.

Ivan8209

Не сработает ни на одном распространённом диалекте.
---
...Я работаю антинаучным аферистом...

Hastya

Я только диалект для ПЭВМ Корвет знаю.

Ivan8209

Не понимаю, они действительно так извратили INTERPRET,
чтобы он понимал ТАКОЕ, или это ты что-то неправильно написал.
---
...Я работаю антинаучным аферистом...

Papazyan

ghc под Линукс пашет отлично, я себе ставил.

Hastya

Насчет циклов я просто не уверен. Не помню.

Ivan8209

Дело не в циклах.
---
...Я работаю антинаучным аферистом...

Barbie29

поиск простых чисел на перле(в определенном диапазоне, в этом примере 1 .. 1000):


#!/usr/bin/perl -sw



use Quantum::Superpositions;



sub is_prime { return $_[0]==2 || $_[0] % all(2..sqrt($_[0])+1) != 0 }



do{print "$_ - простое число  \n" if is_prime($_)} for map {2*$_+1} 1..1000;

еще внизу и факторизация на множители, правда кодировка глючит, руки недойдут исправить

Ivan8209



: sqrt  1 1 >r  begin 2dup > while r> 2 + dup >r + repeat

  2drop r> 1+ 2/ ;

: prime?  dup sqrt  1 >r

  begin dup 1 > while  2dup mod 0<> r> and >r 1- repeat  2drop r> ;

: .primes  1+ 2 ?do  i prime? if i . then loop ;

1000 .primes

Сколько строк кода в твоём "Quantum::Superpositions"?
---
VARIABLE 1

garikus

Component Pascal:


MODULE Primes;



	IMPORT Math, StdLog;



	(* Является ли число x простым ? *)

	PROCEDURE IsPrime* (x: INTEGER): BOOLEAN;

		VAR i, min, max: INTEGER;

	BEGIN

		ASSERT(x > 1);

	

		min := 2;

		max := SHORT(ENTIER(Math.Sqrt(x;

		

		i := min;

		WHILE (i <= max) & (x MOD i # 0) DO

			INC(i)

		END;

		

		RETURN i > max 

	END IsPrime;



	(* Вывод всех простых чисел по n *)

	PROCEDURE OutPrimes* (n: INTEGER);

		VAR i: INTEGER;

	BEGIN

		ASSERT(n > 1);

		

		FOR i := 2 TO n DO

			IF IsPrime(i) THEN

				StdLog.Int(i); StdLog.Tab

			END

		END;

		StdLog.Ln

	END OutPrimes;



END Primes.
"Primes.OutPrimes(100)"
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Marinavo_0507

> Классическим членомерством для Haskell-я является qsort
так же классическим можно назвать и обман, заключённый в этом примере:
сортировка не in-place, поэтому называть это qsort несколько неправомерно

garikus

QuickSort, Component Pascal:
Source:


MODULE Sort;



	PROCEDURE SplitUp (VAR a: ARRAY OF INTEGER; i, j: INTEGER; OUT k: INTEGER);

		VAR pivot, t: INTEGER;

	BEGIN

		ASSERT(j - i > 2);



		pivot := a[i + (j - i) DIV 2];

		WHILE i < j DO

			IF a[i] < pivot THEN

				INC(i)

			ELSIF a[j - 1] > pivot THEN

				DEC(j)

			ELSIF a[i] = a[j - 1] THEN

				INC(i); DEC(j)

			ELSE

				t := a[i]; a[i] := a[j - 1]; a[j - 1] := t;

				INC(i); DEC(j)

			END

		END;



		ASSERTi = j) OR (i = j + 1;

		ASSERT(~(i = j + 1) OR (a[j] = pivot;



		k := i

	END SplitUp;



	PROCEDURE RecSort (VAR a: ARRAY OF INTEGER; i, j: INTEGER);

		VAR k, t: INTEGER;

	BEGIN

		ASSERT(i < j);



		IF j - i = 1 THEN

		ELSIF j - i = 2 THEN

			IF a[i] > a[i + 1] THEN

				t := a[i]; a[i] := a[i + 1]; a[i + 1] := t

			END

		ELSE

			SplitUp(a, i, j, k);

			ASSERTi < k) & (k < j;

			RecSort(a, i, k);

			RecSort(a, k, j)

		END

	END RecSort;



	(* Алгоритм "быстрой" сортировки *)

	PROCEDURE QuickSort* (VAR a: ARRAY OF INTEGER);

	BEGIN

		RecSort(a, 0, LEN(a

	END QuickSort;



END Sort.
Interface:


DEFINITION Sort;



	PROCEDURE QuickSort (VAR a: ARRAY OF INTEGER);



END Sort.

Chupa



			RecSort(a, i, k);

			RecSort(a, k, j)

с таким подходом ему надо O(n) стека, а если делать правильно, то только O(log(n

garikus

а как правильно ?

Chupa

делается только самый короткий из вызовов, а другой разворачивается в цикл

rosali

сортировка не in-place
Почему? Точнее, что ты под этим понимаешь? У тебя просто есть свое представление о том как бы ты стал писать интерпретатор Хаскеля, к семантике Хаскеля как таковой это ведь не имеет отношения...

Marinavo_0507

> Точнее, что ты под этим понимаешь?
> У тебя просто есть свое представление о том как бы ты стал писать
> интерпретатор Хаскеля, к семантике Хаскеля как таковой это ведь не имеет
> отношения...
Конечно, можно себе представить реализацию, которая сделает это in-place.
Но это не будет свойством программы, это будет свойством реализации.
Данное свойство алгоритма применимо только к реализациях на достаточно низкоуровневых языках. Поэтому я и называю данную реализацию на Haskell обманом.

rosali

Простые числа на Haskell-е, сразу все язык то ленивый 
 

sieve (x:xs) = [x' | x'<-xs, x' `mod` x > 0]

primes = map head (iterate sieve [2..])
Prelude> primes[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151
,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,31
3,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,4
91,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,
677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877
,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1
061,1063,1069,1087,1091,1093,{Interrupted!}
Библиотечные функции тоже все совсем не сложные


head (x:xs) = x

map f xs = [f x | x<-xs]

iterate f x = x : iterate f (f x)
PS. Эффективность кстати с перлом не сравнить - это все-таки решето Эратосфена.

garikus

язык простой => компилятор эффективный
может, не надо ничего разворачивать

Chupa

он же не знает какой из вызовов развернуть надо
в лучшем случае компиляторы только самый последний обрабатывают

Marinavo_0507

А если добавить, чтоб тестировалась только делимость на уже найденные простые, не превышающие квадратного корня данного числа?
Тогда можно будет сравнивать эффективность.

Dasar

Задачка 1:
На плоскости размещены кружочки разного диаметра, кружочки не могут друг друга пересекать, или включаться в друг друга.
Кружочки соединены связями.
Связи бывают жесткие и гибкие.
Жесткая связь - не расстягивается, но и не сжимается (железная штанга)
Гибкая связь - не расстягивается, но произвольно сжимается (нитка).
Необходимо спроектировать "модуль", которые выполняет следующие требования:
1. Вывод системы
2. Изменение системы - добавление/удаление кружков и связей с проверкой на корректность
3. Выполнение команд вида - сдвинуть кружок такой-то на такой-то вектор, рассчитав при этом новое положение системы с учетом всех связей.
Дополнительное положение:
Максимально упростить добавление новых видов "кружочков" и новых видов связей.
Усложнения:
1. Есть границы и препятствия - которые не сдвигаются, и мешают движению шариков.
2. Связи полужесткие - имеют длину от a до b
Упрощения:
1. Вместо плоскости - прямая.
2. Точки вместо кружков: кружки не имеют радиуса и могут проходить сквозь друг друга
зы
мне. как постановщику задачи, очень интересно - на сколько сильно можно отделить всю систему от типов связей.

Marinavo_0507

Решение нужно точное или приближённое?
Если приближённое, то можно перейти к дифурам с достаточно гладкой правой частью, и решать их стандартными методами.
Если точное, то скорее всего нужно к символьным вычислениям переходить, и не факт, что получится.

Dasar

Сложная математика нужна даже на прямой?
ps
Мне хочется, в основном, посмотреть как будет организована структура программы, а не расчетная часть

Marinavo_0507

> Мне хочется, в основном, посмотреть как будет организована структура
> программы, а не расчетная часть
Если сводить к дифурам, то структура простейшая получится.
Набор шариков, и набор связей.
Шарик - это несколько переменных, и функция для вывода состояния.
Связь шарика с другим - для каждой переменной по функции, рассчитывающей усилие связи.

koly

Язык brainfuck
Основы
Главная идея Brainfuck - манипулирование памятью. Вам выдается 30.000 массив 1 байтовых блоков, хотя на самом деле размер массива зависит от компилятора или интерпретатора, но стандартный размер - 30.000. Внутри этого массива вы можете увеличивать указатель, значение в ячейке и так далее. Для работы, как я уже говорил, используется 8 операторов:
> = увеличение указателя памяти или смещение право на 1 блок
< = уменьшение или смещение влево на 1 блок
+ = увеличение значения в ячейке памяти, на которую ссылается указатель
- = соответственно уменьшение на единиц
[ = аналог цикла while(cur_block_value != 0)
] = если значение в ячейке на которую указывает указатель не равно нулю, то переход на [
, = аналог getchar ввод одного символа
. = аналог putchar вывод одного сивола на кончоль
Вводные правил
Любые символы кроме описанных выше игнорируются
Все значения в памяти устанавливаются на 0 в начале работы программы
Циклов может быть сколько угодно, однако каждая [ должна заканчиваться]
Примеры:
Давайте напишем программу, которая будет уже 

выводить нечто в консоль, например любимый всеми нами "Hello world". 

Выглядит она так:



>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.

+++++++..+++.[-]>++++++++[<++++>-] <.

>+++++++++++[<++++++++>-]<-.--------.+++

.------.--------.[-]>++++++++[<++++>- ]<+.[-]++++++++++.



  



[/* bf2c.b

  * The omin0us Brainfuck to C interpretor

  * omin0us <gmail.com>

  * 

  * NOTE: This was written just before the release of K-1ine *       and consequently was rushed to be finished. Currently

  *       it does not take well to any characters of input besides

  *       the 8 standard brainfuck operators and newline and EOF.

  *       So consequently, it will only interpret un-commented code.

  *       Check my web site <http://dtors.ath.cx> for a later release 

  *       that will probably have support for commented code. 

  */]





>+++++[>+++++++<-]>.<<++[>+++++[>+++++++<-]<-]>>.+++++.<++[>-----<-]>-.<++

[>++++<-]>+.<++[>++++<-]>+.[>+>+>+<<<-]>>>[<<<+>>>-]<<<<<++[>+++[>---<-]<-

]>>+.+.<+++++++[>----------<-]>+.<++++[>+++++++<-]>.>.-------.-----.<<++[>

>+++++<<-]>>.+.----------------.<<++[>-------<-]>.>++++.<<++[>++++++++<-]>

.<++++++++++[>>>-----------<<<-]>>>+++.<-----.+++++.-------.<<++[>>+++++++

+<<-]>>+.<<+++[>----------<-]>.<++[>>--------<<-]>>-.------.<<++[>++++++++

<-]>+++.---....>++.<----.--.<++[>>+++++++++<<-]>>+.<<++[>+++++++++<-]>+.<+

+[>>-------<<-]>>-.<--.>>.<<<+++[>>++++<<-]>>.<<+++[>>----<<-]>>.++++++++.

+++++.<<++[>---------<-]>-.+.>>.<<<++[>>+++++++<<-]>>-.>.>>>[-]>>[-]<+[<<[

-],[>>>>>>>>>>>>>+>+<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>[<<<<<<<<<<<<<<+>>>>>>>>

>>>>>>-]<<+>[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-

[-[-[-[-[-[-[-[-[-[-[-[<->[-]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]<[

<<<<<<<<<<<<[-]>>>>>>>>>>>>[-]]<<<<<<<<<<<<[<+++++[>---------<-]>++[>]>>[>

+++++[>+++++++++<-]>--..-.<+++++++[>++++++++++<-]>.<+++++++++++[>-----<-]>

++.<<<<<<.>>>>>>[-]<]<<<[-[>]>>[>++++++[>+++[>++++++<-]<-]>>++++++.-------

------.----.+++.<++++++[>----------<-]>.++++++++.----.<++++[>+++++++++++++

++++<-]>.<++++[>-----------------<-]>.+++++.--------.<++[>+++++++++<-]>.[-

]<<<<<<<.>>>>>]<<<[-[>]>>[>+++++[>+++++++++<-]>..---.<+++++++[>++++++++++<

-]>.<+++++++++++[>-----<-]>++.<<<<<<.>>>>>>[-]<]<<<[-[>]>>[>+++[>++++[>+++

+++++++<-]<-]>>-.-----.---------.<++[>++++++<-]>-.<+++[>-----<-]>.<++++++[

>----------<-]>-.<+++[>+++<-]>.-----.<++++[>+++++++++++++++++<-]>.<++++[>-

----------------<-]>.+++++.--------.<++[>+++++++++<-]>.[-]<<<<<<<.>>>>>]<<

<[<+++[>-----<-]>+[>]>>[>+++++[>+++++++++<-]>..<+++++++[>++++++++++<-]>---

.<+++++[>----------<-]>---.<<<<<<.>>>>>>[-]<]<<<[--[>]>>[>+++++[>+++++++++

<-]>--..<+++++++[>++++++++++<-]>-.<+++++[>----------<-]>---.[-]<<<<<<.>>>>

>]<<<[<+++[>----------<-]>+[>]>>[>+++[>++++[>++++++++++<-]<-]>>-.<+++[>---

--<-]>.+.+++.-------.<++++++[>----------<-]>-.++.<+++++++[>++++++++++<-]>.

<+++++++[>----------<-]>-.<++++++++[>++++++++++<-]>++.[-]<<<<<<<.>>>>>]<<<

[--[>]>>[>+++++[>+++++[>+++++<-]<-]>>.[-]<<<<<<<.>>>>>]<<<[<++++++++++[>--

--------------<-]>--[>]>>[<<<<[-]]]]]]]]]]]>>]<++[>+++++[>++++++++++<-]<-]

>>+.<+++[>++++++<-]>+.<+++[>-----<-]>.+++++++++++.<+++++++[>----------<-]>

------.++++++++.-------.<+++[>++++++<-]>.<++++++[>+++++++++++<-]>.<+++++++

+++.

Dasar

Что будет, если функция связи будет негладкая, разрывная или дискретная?

Marinavo_0507

Нужно искать приближения, достаточно гладкие для выбранного метода.
Это нужно делать для добавления нового вида связи.
Если захочется ещё и погрешность оценивать, то надо ещё подумать, и либо самому выводить оценки для каждого типа связи, или программу заставить, опять же введя символьные вычисления.

enochka1145

Это случаем не из интегральных микросхем взято? Или из других САПР или ГИС?
Мне нравится пример (наконец-то не чистая математика, где Java явно не чемпион но хотелось бы больше конкретики.

Papazyan

Требование 3 определено некоректно. Не определено, что понимается под словом сдвинуть. Есть по меньшей мере три интерпретации:
1) телепортировать кружок
2) двигать его по прямой
3) двигать по кривой
Кроме того, решение в данном случае не единственное даже без учета поворотов.

Papazyan

Вот brainfuck-машины, кстати. (взял с другого форума).

Dasar

Двигать по прямой.
> Кроме того, решение в данном случае не единственное даже без учета поворотов
Попробовать приблизиться к реалу.

Dasar

> Это случаем не из интегральных микросхем взято? Или из других САПР или ГИС?
нет.
> Мне нравится пример (наконец-то не чистая математика, где Java явно не чемпион но хотелось бы больше конкретики.
Попробуй доопределить сам
Оставить комментарий
Имя или ник:
Комментарий: