Jak ustalić, czy liczba jest nieparzysta, czy nawet bez operacji modowo-bitowych? [Zamknięte]

19

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.

Wayne Hartman
źródło
3
Czy powinniśmy stworzyć funkcję czy program? Jak powinno wyglądać IO, jeśli musimy zrobić program? Proszę rozwinąć dalej.
Juan
2
Jakie obiektywne kryterium określi przyjętą odpowiedź? Rozmiar kodu? Coś innego?
PleaseStand
Czy to zdecydowanie liczba? Czy powinno dawać fałszywe alarmy dla łańcucha?
William
Działo się to już od dłuższego czasu, ale nie wydaje się, aby istniał jakikolwiek warunek wygranej, co moim zdaniem oznacza, że ​​nie ma tu żadnej gry.
dmckee,

Odpowiedzi:

40

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

(i/2)*2==i
fR0DDY
źródło
6
Niekoniecznie większość, powiedziałbym. Może wielu.
Joey,
1
aby upewnić się, że działa poprawnie, musisz upewnić się, że wszystko przerzuciłeś na typ int/long
warren
@warren Zależy od języka programowania / optymalizacji kompilatora / etc. Dodatkowo możesz użyć floor(). Działa to doskonale w C i C ++.
Mateen Ulhaq
1
Czy 0 jest liczbą parzystą?
użytkownik nieznany
4
@userunknown: Tak, zero jest parzyste.
Keith Thompson,
71

Pyton

print('even' if (-1)**n==1 else 'odd')
dan04
źródło
10
Prosta piękność / piękna prostota matematyki ... bardzo miło!
jscs
Ten bardzo mi się podoba.
Rob
Powolny, ale kreatywny.
Mateen Ulhaq
21

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.
Peter Olson
źródło
21

Matematyka

SawtoothWave[x / 2] == 0
Exp[I Pi x] - 1 == 0
Sin[5 x / Pi] == 0
Ming-Tang
źródło
2
Czy możesz podzielić te dwa rozwiązania na różne odpowiedzi?
FUZxxl
Czy to nie cztery rozwiązania?
Joey,
W rzeczywistości wszystkie wbudowane nazwy w Mathematica są pisane wielkimi literami, więc tak zabawnie, jak to wygląda, powinieneś używać Ii Pizamiast ii pi.
David Zhang
15

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;
}
aaaaaaaaaaaa
źródło
Pamiętaj, aby używać liczb całkowitych bez znaku. Przepełnienie podpisanymi liczbami całkowitymi jest niezdefiniowanym zachowaniem w C, więc optymalizacja mogłaby zrobić coś dziwnego, gdyby tego chciała.
Joey Adams,
13

Python (wolny)

n=1234
while n > 1: n -= 2 #slow way of modulus.
print "eovdedn"[n::2]
st0le
źródło
1
Działa pozytywnie ... przypuszczam, że mógłbym dodać abs()połączenie na początku.
st0le
@Josh: Ta sztuczka pojawiła się tutaj już kilka razy :)
Joey,
Kredyty dla gnibblr :)
st0le
@Joey: Nie sądziłem, że to nowy, ale styl nie musi być oryginalny. :)
jscs
12

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).

Proszę wstać
źródło
2
Aby spełnić wymóg „funkcji”, możesz zmienić go na prosty /[02468]$/.test.
Ry-
To nie było dokładnie wyczyścić w pytaniu, ale może się zdarzyć, że wejście nie jest liczbą w ogóle /[02468]$/.test('I am a fake even number 0'). W takim przypadku możesz zrobić/^[0-9].[02468]$/.test(i)
William
/-?^\d*[02468]$/byłoby trochę bardziej rygorystyczne niż twoje wyrażenie regularne. Będziesz potrzebował więcej pracy, aby działało to poprawnie dla liczb, które są znakowane przy użyciu notacji naukowej.
Thomas Eding
12

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"
jscs
źródło
Ładne rozwiązania :-)
Joey
2
Naprawdę stara nekro, ale czy domysł Goldbacha nie odpowiada nawet na 9? Wygląda to na przypadek potwierdzenia wynikającego z tego błędu
March Ho
Tak, masz absolutną rację w stu procentach, @MarchHo. Jajko na mojej twarzy.
jscs
10

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

źródło
wygląda mi dłużej niż odpowiedź GolfScript
warren
2
Miałem na myśli pierwszy blok ( odd), który jest wbudowaną funkcją, która zwraca True, jeśli liczba jest nieparzysta. To kompletna odpowiedź sama w sobie i krótsza niż obecna odpowiedź GolfScript (która w chwili pisania tego tekstu ma 10 znaków, ale spodziewam się, że spadnie). Pytanie jest również nieco nieokreślone, dlatego twierdzę, że oddjest wystarczające. To również może się zmienić.
1
przegapiłem pierwszą odpowiedź w swojej odpowiedzi :)
warren
1
parityAlgorytm działa przynajmniej na wszystkich Numinstancjach, które są liczbami całkowitymi. To jest gorące! Chociaż pewnie bym to zrobił evens = [0,2..] >>= \n -> [-n, n]. Podobne dla kursów.
Thomas Eding
7

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;
}
Keith Thompson
źródło
Pytanie wymienia liczbę, a nie liczbę całkowitą. Liczba jak 0.5zwroty, truekiedy nie powinna.
Konrad Borowski
6

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 3 ).


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.

przestał się obracać w lewo
źródło
5

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.

Joey
źródło
5

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.
ReyCharles
źródło
4

Rubin

n.odd?

Jeśli chcesz wydrukować wynik:

f[n] = ->(n){puts n.odd?? 'odd' : 'even'}
Lowjacker
źródło
Dość używam ruby ​​używa mod w .odd?definicji.
MrZander
4

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
JB
źródło
3

Golfscript

~,2/),1=\;
TY
źródło
3

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.

jscs
źródło
3
Zero jest zdecydowanie równe. Zobacz także: en.wikipedia.org/wiki/Parity_of_zero
@jloy: Aw, bzdury. Myślałem, że to „funkcja, a nie błąd”. Więcej poprawek ...
jscs
3

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.

Howard
źródło
3

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
FUZxxl
źródło
3

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)))
Samuel Duclos
źródło
3

Perl

Co powiesz na

use Math::Trig;
print(cos(pi*@ARGV[0])>0?"even":"odd")
ShaiDeshe
źródło
2

JavaScript, 36

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

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

Ry-
źródło
2

Perl

$n x '0' =~ /^(00)*$/
Ming-Tang
źródło
2

Pyton

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

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

gnibbler
źródło
2

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)
paproć
źródło
2

Clojure

  (defmacro even?[n]
  `(= 1 ~(concat (list *) (repeat n -1))))
Benjie Holson
źródło
2

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
Brian Vandenberg
źródło
BTW shli przyjaciele są niedozwoleni ...
FUZxxl
2

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.

Skizz
źródło
2

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.

scleaver
źródło
2

Q

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

{1b$-[;2]/[2<=;abs x]}
skeevey
źródło