Jak ustalić, czy liczba jest nieparzysta, czy nawet bez operacji modowo-bitowych?

To wyzwanie jest rażąco nieefektywne, ale podważa twoją zdolność do myślenia nieszablonowego na rzecz kreatywnego rozwiązania.

EDYTOWAĆ :

Proszę utworzyć funkcję. Ponadto, chociaż wyrażenie regularne jest zabawną odpowiedzią, funkcja powinna akceptować każdy prawidłowy numer.

TŁO : To pytanie pochodzi z moich najwcześniejszych dni programowania. Zadaniem domowym na nasz pierwszy dzień zajęć było napisanie prostego programu, który drukował „nieparzyste” lub „parzyste”. Jako bachor, którym byłem, nie przeczytałem książki, którą mieliśmy dla klasy, w której po prostu pokazał nam, jak jej używać% . Spędziłem około pół godziny krocząc do przodu w swoim pokoju, próbując wymyślić sposób na zrobienie tego, i przypomniałem sobie z wykładu, że liczby mogą stracić i zyskać precyzję, gdy są przenoszone z jednego prymitywnego typu na inny. Dlatego, jeśli weźmiesz liczbę, podzielisz ją przez dwa, a następnie pomnożysz z powrotem, nie będzie równa pierwotnej liczbie, będziesz wiedział, że liczba była nieparzysta.

Następnego dnia byłem oszołomiony, gdy nasz instruktor oceniał nasze programy, że uznał, że jest to najbardziej oryginalny, choć nieefektywny sposób rozwiązania problemu.

W większości języków programowania podział zwraca iloraz liczb całkowitych. Możesz to po prostu sprawdzić

(i/2)*2==i

Pyton

print('even' if (-1)**n==1 else 'odd')

Brainf *** (179)

Jest to jeden z bardziej interesujących problemów związanych z logiką warunkową, które zrobiłem w BF.

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

Wymaga wprowadzania tekstu za pomocą liczby. Jeśli liczba jest parzysta, wyprowadza E, a jeśli jest nieparzysta, wyprowadza O.

Jestem z tego wystarczająco dumny, że pokażę bardziej czytelną dla człowieka formę:

+[>,]                                                   steps through input until it reaches eof.
<---------------------------------------                gets the numerical value of the last digit
>>+++++[>+++++++++++++>+++++++++++++++<<-]>++++>++++    store E and O
<<+<+<                                                  store a bit indicating parity, and a temporary bit
-[>-<                                                   !1
  -[>+<                                                 && !2
    -[>-<                                               && !3
      -[>+<                                             && !4
        -[>-<                                           && !5
          -[>+<                                         && !6
            -[>-<                                       && !7
              -[>+<                                     && !8
                -[>-<[-]]                               && !9
              ]
            ]
          ]
        ]
      ]
    ]
  ]
]
>[>>>.<<-<-]>[>.<-]                                     Display E or O based on the value of the parity bit.

Matematyka

SawtoothWave[x / 2] == 0
Exp[I Pi x] - 1 == 0
Sin[5 x / Pi] == 0

do

Kilkakrotnie pomnożona przez siebie dowolna liczba parzysta przepełni się do 0, biorąc pod uwagę liczbę całkowitą o skończonym rozmiarze, a każda liczba nieparzysta będzie nadal mieć ustawiony co najmniej najmniej znaczący bit.

#include "stdio.h"
long long input=123;
int main(){
    int a;
    for(a=6;a;a--){
        input*=input;
    }
    if(input){
        printf("Odd");
    }
    else{
        printf("Even");
    }
    return 0;
}

Edycja: jako prosta funkcja:

int isOdd(long long input){
    int a;
    for(a=6;a;a--){
        input*=input;
    }
    return !!input;
}

Python (wolny)

n=1234
while n > 1: n -= 2 #slow way of modulus.
print "eovdedn"[n::2]

JavaScript

/[02468]$/.test(i)

daje trueliczbę parzystą. Działa to tylko z liczbami całkowitymi o rozsądnej wielkości (np. Nie notacja naukowa po konwersji na ciąg i brak części ułamkowej).

Pyton

Ponieważ nie jestem do końca pewien, jakie są kryteria punktacji, oto kilka rozwiązań, które wymyśliłem dla rozrywki. Większość z nich korzystaabs(n) obsługuje liczby ujemne. Większość, jeśli nie wszystkie, nigdy nie powinna być używana do prawdziwych obliczeń.

Ten jest nudny:

from __future__ import division
def parity(n):
    """An even number is divisible by 2 without remainder."""
    return "Even" if n/2 == int(n/2) else "Odd"

def parity(n):
    """In base-10, an odd number's last digit is one of 1, 3, 5, 7, 9."""
    return "Odd" if str(n)[-1] in ('1', '3', '5', '7', '9') else "Even"

def parity(n):
    """An even number can be expressed as the sum of an integer with itself.

    Grossly, even absurdly inefficient.

    """
    n = abs(n)
    for i in range(n):
        if i + i == n:
            return "Even"
    return "Odd"

def parity(n):
    """An even number can be split into two equal groups."
    g1 = []
    g2 = []
    for i in range(abs(n)):
        g1.append(None) if len(g1) == len(g2) else g2.append(None)
    return "Even" if len(g1) == len(g2) else "Odd"

import ent # Download from: http://wstein.org/ent/ent_py
def parity(n):
    """An even number has 2 as a factor."""
    # This also uses modulo indirectly
    return "Even" if ent.factor(n)[0][0] == 2 else "Odd"

I to jest moje ulubione, chociaż niestety nie działa (jak wskazał March Ho poniżej: tylko dlatego, że wszystkie liczby parzyste są sumą dwóch liczb pierwszych, nie oznacza, że ​​nie wszystkie liczby nieparzyste).

import itertools
import ent    # Download from: http://wstein.org/ent/ent_py
def parity(n)
    """Assume Goldbach's Conjecture: all even numbers greater than 2 can
    be expressed as the sum of two primes.

    Not guaranteed to be efficient, or even succeed, for large n.

    """
    # A few quick checks
    if n in (-2, 0, 2): return "Even"
    elif n in (-1, 1): return "Odd"
    if n < 0: n = -n    # a bit faster than abs(n)
    # The primes generator uses the Sieve of Eratosthenes
    # and thus modulo, so this is a little bit cheating
    primes_to_n = ent.primes(n)
    # Still one more easy way out
    if primes_to_n[-1] == n: return "Odd"
    # Brutish!
    elif n in (p1+p2 for (p1, p2) in itertools.product(primes_to_n, primes_to_n)):
        return "Even"
    else:
        return "Odd"

Haskell

To oczywiście nie jest kreatywne, nieszablonowe rozwiązanie, którego szukasz, ale ile razy mam zamiar opublikować odpowiedź Haskell krótszą niż GolfScript, naprawdę? Szkoda, że ​​to nie jest golf golfowy.

odd

Ale poważniej:

data Parity = Even | Odd
            deriving (Show)

parity = p evens odds
  where p (x:xs) (y:ys) i | i == x = Even
                          | i == y = Odd
                          | otherwise = p xs ys i
        evens = interleave [0,2..] [-2,-4..]
        odds = interleave [1,3..] [-1,-3..]
        interleave (x:xs) ys = x : interleave ys xs

Używając celowo przewrotnej interpretacji pytania „Jak ustalić, czy liczba jest nieparzysta, czy parzysta”, oto implementacja C (załóż booli trueodpowiednio zdefiniuj):

bool is_odd_or_even(int n)
{
    return true;
}

Co, nie ma jeszcze algorytmów losowych?

do

#include<stdio.h>
#include<stdlib.h>

void prt_parity_of(int n){
  int i,j=2;
  char o[]="eovdedn"
     , f[n=abs(n)]; for(i=n;i-->0;f[i]=1);

  while(j>1){
    while((i=rand()%n)
       == (j=rand()%n)
       || (f[i]&f[j]>0)
       && (f[i]=f[j]=0)
    );for(i=j=0; ++i<n; j+=f[i])
  ;}for(;j<7;j+=2)putchar(o[j]);
}

Losowo paruj liczby w zakresie 0 .. n -1, aż pozostanie mniej niż 2. Jest to dość niezwykle nieefektywne: O ( n ³ ).

Zupełnie inny:

Haskell

import Data.Complex

ft f = (\ω -> sum[ f(t) * exp(0:+2*pi*ω*t) | t<-[-1,-0.9..1] ] )

data Parity = Even | Odd deriving (Show)

parity n
  | all (\(re:+im) -> abs re > abs im) [ft ((:+0).(^^n)) ω | ω<-[0..20]]  = Even
  | otherwise                                                             = Odd

Wykorzystuje fakt, że transformata Fouriera funkcji parzystej (np. \x->x^^4) Jest rzeczywista, podczas gdy transformata Fouriera funkcji nieparzystej jest urojona.

Windows PowerShell

function OddOrEven([long]$n) {
  if (0,2,4,6,8 -contains "$n"[-1]-48) {
    "Even"
  } else {
    "Odd"
  }
}

1. Konwertuj na ciąg
2. Wybierz ostatnią literę (cyfrę) (zasadniczo mod 10).
3. Sprawdź, czy jest to 0, 2, 4, 6 lub 8.

Bez operatorów bitowych, bez modułu, zgodnie z żądaniem.

Coq, 103

Fixpoint even n:=match n with O=>true|S n=>odd n end with odd n:=match n with O=>false|S n=>even n end.

O ile mogę to stwierdzić, jest to pierwszy wpis w coq na codegolf.

Jeszcze krótszy (59):

Fixpoint even n:=match n with O=>true|S n=>negb(even n)end.

Rubin

n.odd?

Jeśli chcesz wydrukować wynik:

f[n] = ->(n){puts n.odd?? 'odd' : 'even'}

Unlambda

Świat potrzebuje więcej Unlambda.

Unlambda ma tutaj przewagę zabójcy: domyślną ( ahem ) reprezentacją liczb są cyfry kościelne, więc wszystko, czego potrzeba, to zastosować je do funkcji binarnej, aby nie działała jako prawda. Łatwo!

PS: Markdown i Unlambda zdecydowanie nie są stworzone dla siebie.

true  = i
false = `ki
not   = ``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki
even? = ``s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`ki

Weryfikacja pierwszych kilku liczb całkowitych:

```s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`ki`ki                   => i
```s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`kii                     => `ki
```s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`ki``s``s`kski           => i
```s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`ki``s``s`ksk``s``s`kski =>`ki

Golfscript

~,2/),1=\;

Pyton

print (["even"] + (["odd", "even"] * abs(n)))[abs(n)]

Podobna wydajność do wcześniejszej wersji. Działa teraz na 0.

Niepoprawna wcześniejsza wersja:

print ((["odd", "even"] * abs(n))[:abs(n)])[-1]

Niezbyt wydajny; czas i pamięć oczywiście O (n): 32 milisekundy na 1 000 000; 2,3 ms na 100000; 3.2 usec dla 100. Działa z liczbami ujemnymi. Zgłasza błąd dla 0, ponieważ 0 nie jest parzyste ani nieparzyste.

Fraktran

[65/42,7/13,1/21,17/7,57/85,17/19,7/17,1/3]

dotyczyło

63*2^abs(n)

daje albo 5jeśli njest nieparzysty albo1 jeśli njest parzysty.

Aktualizacja : Znacznie krótsza, ale nie tak interesująca:

[1/4](2^abs(n))

jest 2na nieparzyste ni 1na parzyste n.

MMIX (4 bajty)

To rodzaj oszustwa. Nie używam ani modów, ani bitów. To raczej wbudowane testowanie liczb nieparzystych / parzystych. Zakładając, że $3zawiera liczbę do przetestowania, a wynik przechodzi do$2 :

ZSEV $2,$3,1

ustawia $2na 1if $3jest parzyste, a 0jeśli nie. Mnemnoric ZSEVoznacza nawet zero i ma następującą semantykę:

ZSEV a,b,c: if (even b) a = c; else a = 0;

Dla powyższej linii mmixalgeneruje te cztery bajty zestawu:

7F 02 03 01

Schemat

To najbardziej nieefektywne rozwiązanie, jakie znam.

(letrec ([even? (lambda (n)
                 (if (zero? n) "even"
                     (odd? (- n 2))))]
         [odd? (lambda (n)
                 (if (= n 1) "odd"
                     (even? (- n 2))))])
  (even? (read)))

Perl

Co powiesz na

use Math::Trig;
print(cos(pi*@ARGV[0])>0?"even":"odd")

JavaScript, 36

function(i){while(i>0)i-=2;return!i}

Zwraca, truejeśli nawet, falsejeśli nie.

Perl

$n x '0' =~ /^(00)*$/

Pyton

zip((False, True)*(i*i), range(i*i))[-1][0]

testowanie kwadratu i, więc działa również dla liczb ujemnych

FA#

Wzajemna rekurencja dla wygranej.

Liczba n jest nawet jeśli jest zerowa lub (n-1) jest nieparzysta.

Liczba n jest nieparzysta, jeśli jest nierówna do zera, a (n-1) jest parzysta.

(abs dodane, jeśli ktoś jest zainteresowany parzystością liczb ujemnych)

let rec even n = n = 0 || odd (abs n - 1) 
    and odd n = n <> 0 && even (abs n - 1)

Clojure

  (defmacro even?[n]
  `(= 1 ~(concat (list *) (repeat n -1))))

Co kwalifikuje się jako operacje bitowe? Pod maską dzielenie liczb całkowitych przez 2 prawdopodobnie będzie realizowane jako przesunięcie bitowe.

Zakładając, że przesunięcia bitów nie są wykluczone:

C / C ++

(unsigned char)((unsigned char)(n > 0 ? n : -n) << 7) > 0 ? "odd" : "even"

edytuj Pominięto niektóre nawiasy i ostatecznie zmieniono, aby usunąć zmianę, aby zrobić mniej. Możesz to przetestować, wykonując następujące czynności (w * nix):

echo 'main(){ std::cout<< (unsigned char)((unsigned char)(n > 0 ? n : -n) << 7) > 0 \
        ? "odd\n" : "even\n";}' \
  | gcc --include iostream -x c++ -o blah -
./blah

... chociaż w Linuksie / tcsh musiałem uciec przed odwrotnym ukośnikiem, \nnawet jeśli był to pojedynczy cudzysłów. Testowałem w Little & Big-Endian, działa poprawnie w obu. Również ręcznie to skopiowałem; komputer, z którym piszę, nie ma kompilatora, więc mogą mieć błędy.

x86 asm

            mov eax, n          # Get the value
            cmp eax,0           # Is it zero?
            jge pos_label       # If >= 0, skip the next part
            neg eax
pos_label:

.

            imul al, 128

lub

            shl  al, 7

lub

            lea  eax, [eax*8]    # Multiply by 2^3 (left-shift by 3 bits)
            lea  eax, [eax*8]    # ... now it's n*2^6
            lea  eax, [eax*2]    # ... 2^7, or left-shift by 7 bits

... śledzony przez:

            cmp al,  0          # Check whether the low byte in the low word is zero or not
            jz  even_label      # If it's zero, then it was an even number
            odd_label           # ... otherwise it wasn't

Alternatywnie, zmiany i porównania można również wykonać w ten sposób:

            sar al,1            # signed integer division by 2 on least-significant byte
            jc  odd_label       # jump if carry flag is set

W procesorze 68000 możesz przenieść wartość słowa z adresu zdefiniowanego przez wartość do przetestowania:

 move.l <number to test>,a0
 move.w (a0),d0
 ; it's even if the next instruction is executed

i niech pułapka sprzętowa dla błędu adresu określa nieparzystą / parzystą naturę wartości - jeśli wyjątek zostanie zgłoszony, wartość była nieparzysta, jeśli nie, wartość była parzysta:

 <set up address error trap handler>
 move.l <pointer to even string>,d1
 move.l <number to test>,a0
 move.w (a0),d0
 <reset address error trap handler>
 <print string at d1>
 <end>

 address_error_trap_handler:
 move.l <pointer to odd string>,d1
 rte

Nie działa na procesorach Intel x86, ponieważ są one bardziej elastyczne w zakresie dostępu do danych.

Pyton

Postanowiłem spróbować najbrzydszego, najbardziej zagmatwanego rozwiązania, jakie mogłem wymyślić:

n=input();r=range(n+1)
print [j for i in zip(map(lambda x:str(bool(x))[4],[8&7for i in r]),
map(lambda x:str(x)[1],[[].sort()for x in r])) for j in i][n]

Drukuje e, jeśli parzyste, a jeśli nieparzyste.

Q

Odejmuj 2, aż x <2, a następnie przelicz na bool

{1b$-[;2]/[2<=;abs x]}