Изучение F# - печатающий простые числа
Так как приведенный ниже метод (с использованием XOR ) для обращения строки не указан, я прилагаю этот метод для обращения строки.
Алгоритм основан на:
1. (A XOR B) XOR B = A
2. (A XOR B) XOR A = B
Фрагмент кода:
public class ReverseUsingXOR {
public static void main(String[] args) {
String str = "prateek";
reverseUsingXOR(str.toCharArray());
}
/*Example:
* str= prateek;
* str[low]=p;
* str[high]=k;
* str[low]=p^k;
* str[high]=(p^k)^k =p;
* str[low]=(p^k)^p=k;
*
* */
public static void reverseUsingXOR(char[] str) {
int low = 0;
int high = str.length - 1;
while (low < high) {
str[low] = (char) (str[low] ^ str[high]);
str[high] = (char) (str[low] ^ str[high]);
str[low] = (char) (str[low] ^ str[high]);
low++;
high--;
}
//display reversed string
for (int i = 0; i < str.length; i++) {
System.out.print(str[i]);
}
}
}
Выход:
keetarp
5 ответов
Вот простая реализация Решета Эратосфена на F #:
let rec sieve = function
| (p::xs) -> p :: sieve [ for x in xs do if x % p > 0 then yield x ]
| [] -> []
let primes = sieve [2..50]
printfn "%A" primes // [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47]
Эта реализация не будет работать для очень больших списков, но она иллюстрирует элегантность функциональности раствор.
Вы определенно не хотите учиться на этом примере, но я написал реализацию на F # сита NewSqueak , основанную на передаче сообщений:
type 'a seqMsg =
| Die
| Next of AsyncReplyChannel<'a>
type primes() =
let counter(init) =
MailboxProcessor.Start(fun inbox ->
let rec loop n =
async { let! msg = inbox.Receive()
match msg with
| Die -> return ()
| Next(reply) ->
reply.Reply(n)
return! loop(n + 1) }
loop init)
let filter(c : MailboxProcessor<'a seqMsg>, pred) =
MailboxProcessor.Start(fun inbox ->
let rec loop() =
async {
let! msg = inbox.Receive()
match msg with
| Die ->
c.Post(Die)
return()
| Next(reply) ->
let rec filter' n =
if pred n then async { return n }
else
async {let! m = c.AsyncPostAndReply(Next)
return! filter' m }
let! testItem = c.AsyncPostAndReply(Next)
let! filteredItem = filter' testItem
reply.Reply(filteredItem)
return! loop()
}
loop()
)
let processor = MailboxProcessor.Start(fun inbox ->
let rec loop (oldFilter : MailboxProcessor<int seqMsg>) prime =
async {
let! msg = inbox.Receive()
match msg with
| Die ->
oldFilter.Post(Die)
return()
| Next(reply) ->
reply.Reply(prime)
let newFilter = filter(oldFilter, (fun x -> x % prime <> 0))
let! newPrime = oldFilter.AsyncPostAndReply(Next)
return! loop newFilter newPrime
}
loop (counter(3)) 2)
member this.Next() = processor.PostAndReply( (fun reply -> Next(reply)), timeout = 2000)
interface System.IDisposable with
member this.Dispose() = processor.Post(Die)
static member upto max =
[ use p = new primes()
let lastPrime = ref (p.Next())
while !lastPrime <= max do
yield !lastPrime
lastPrime := p.Next() ]
Это работает?
> let p = new primes();;
val p : primes
> p.Next();;
val it : int = 2
> p.Next();;
val it : int = 3
> p.Next();;
val it : int = 5
> p.Next();;
val it : int = 7
> p.Next();;
val it : int = 11
> p.Next();;
val it : int = 13
> p.Next();;
val it : int = 17
> primes.upto 100;;
val it : int list
= [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]
Милая! :)
Использование функции Sieve, такой как Eratosthenes , - хороший способ. Функциональные языки очень хорошо работают со списками, так что я бы начал с этого в виду структуры.
С другой стороны, функциональные языки хорошо построены из функций (хех). Для «ощущения» функционального языка я бы создал функцию Sieve, а затем вызвал бы ее для вывода простых чисел. Вы даже можете разделить его: одна функция создает список и выполняет всю работу, а другая выполняет всю печать, аккуратно разделяя функции.
Здесь есть пара интересных версий . И есть хорошо известные реализации на других подобных языках. Вот один в OCAML, который превосходит другого в C.
Simple but inefficient suggestion:
- Create a function to test whether a single number is prime
- Create a list for numbers from 2 to 100
- Filter the list by the function
- Compose the result with another function to print out the results
To make this efficient you really want to test for a number being prime by checking whether or not it's divisible by any lower primes, which will require memoisation. Probably best to wait until you've got the simple version working first :)
Let me know if that's not enough of a hint and I'll come up with a full example - thought it may not be until tonight...
Вот мой старый пост на HubFS об использовании рекурсивных последовательностей для реализации генератора простых чисел.
Если вам нужна быстрая реализация, есть хороший OCaml code by Markus Mottl
PS, если вы хотите перебрать простое число до 10 ^ 20, вы действительно хотите перенести primegen от DJ Bernstein на F # / OCaml :)