k-girdili bir ikili doğruluk tablosu, k girdi bitini (ikili rakamlar, 0[yanlış] veya 1[doğru]) tek bir çıktı bitine resmeden bir fonksiyondur.
Örneğin, VE ve XOR mantıksal operatörleri için 2-girdili ikili doğruluk tablosu aşağıda veriliyor:
| x | y | x VE y |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| x | y | x XOR y |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Her (a, b, c, d, e, f) 6-bitlik girdi için,
τ(a, b, c, d, e, f) VE τ(b, c, d, e, f, a XOR (b VE c)) = 0
eşitliğini sağlayan 6-girdili kaç ikili τ doğruluk tablosu vardır?Cevap: 15964587728784
Java:
public class Euler209 {
Euler209(){
int[] nextNumber = new int[64];
for( int i=0; i<64; i++ ){
boolean a = (i&32)!=0;
boolean b = (i&16)!=0;
boolean c = (i& 8)!=0;
nextNumber[i] = ((i&31)<<1) + ((a^(b&c))?1:0);
}
// count loop lengths
ArrayList<Integer> loops = new ArrayList<Integer>();
for( int done = 0; done<64; ){
// find first unused entry
int r=0;
while( nextNumber[r]<0 ) r++;
// follow loop around
int count = 0;
while( nextNumber[r]>=0 ){
int r2 = nextNumber[r];
nextNumber[r] = -1;
count++;
done++;
r = r2;
}
loops.add(count);
}
// each loop may have any number of bits set, but no adjacent ones.
Pascal pas = new Pascal();
long count = 1;
for (int looplen : loops) {
long loopcount = 0;
for( int num = 0; num*2<=looplen; num++ ){
// count number of ways to distribute num non-adjacent bits amongst loop of length looplen
// == count number of ways to have first bit set, and num-1 non-adjacent bits on strip of length looplen-3
// + number of ways to have first bit clear, and num non-adjacent bits on strip of length looplen-1
// == count number of ways to have first bit set, and num-1 bits on strip of length looplen-3 +1-(num-1)
// + number of ways to have first bit clear, and num bits on strip of length looplen-1 +1-num
//
long c = pas.nChooseR(looplen-num-1, num-1) + pas.nChooseR(looplen-num, num);
loopcount += c;
}
count *= loopcount;
}
System.out.println(count);
}
} C++:#include <stdio.h>
long long dp[65][2][2];
bool vis[64] = {0};
int cycleLength(int t){
for (int len=0; ; len++){
if (vis[t]) return len;
else vis[t] = 1;
int a = (t&(1<<0))?1:0;
int b = (t&(1<<1))?1:0;
int c = (t&(1<<2))?1:0;
t = (t>>1) | ((a^(b&c))<<5);
}
}
long long rec(int L, int P, int S){
if (L==0) return P!=S || P==0;
if (dp[L][P][S]) return dp[L][P][S];
return dp[L][P][S] = rec(L-1,0,S) + (1-P) * rec(L-1,1,S);
}
int main(){
long long res = 1;
for (int i=0; i<(1<<6); i++){
int L = cycleLength(i);
if (L==0) continue;
res *= rec(L-1,0,0) + rec(L-1,1,1);
}
printf("%lld\n",res);
} Maple:> with(Bits):
> Next:=t->[t[2..6][],Xor(t[1],And(t[2],t[3]))]:
> Chain:=proc(t)
> local T,l;
> T:=Next(t); l:=t;
> while T<>t do
> l:=l,T; T:=Next(T); od;
> return [l];
> end:
>
> tGen:=NULL: tMet:=[NULL]:
> while nops(tMet)<>64 do
> nr:=[seq(rand(2)(),i=1..6)];
> if not nr in tMet then
> tGen:=tGen,nr;
> tMet:=[tMet[],Chain(nr)[]];
> fi
> od:
> tGen:=[tGen]:
>
> np:=proc(n,prev,sfirst)
> option remember;
> if n=0 then return 1-And(prev,sfirst) fi;
> if prev=1 then return np(n-1,0,sfirst) fi;
> return np(n-1,0,sfirst)+np(n-1,1,sfirst)
> end:
>
> nf:=n->np(n-1,0,0)+np(n-1,1,1):
>
> mul(nf(nops(Chain(i))),i in tGen); Mathematica:
Times @@ (Sum[
Binomial[# - r + 1, r] - Binomial[# - r - 1, r - 2], {r, 0,
Floor[#/2]}] & /@
Length /@
ToCycles[
FromDigits[#,
2] & /@ (Module[{list = RotateLeft[#]},
list[[-1]] =
list[[-1]] \[Xor] (list[[1]] \[And] list[[2]]); list] & /@
Tuples[{False, True}, 6] /. {True -> 1, False -> 0}) + 1]) Pyhton:from tools import timer
@timer
def p209(N):
def circular_logic(n):
dp={(1,):1, (0,):1}
for x in xrange(n-1):
ndp = {}
for prev, v in dp.iteritems():
for nxt in xrange(2):
if not prev[-1] & nxt:
ndp.setdefault(prev[:1] + (nxt,), 0)
ndp[prev[:1] + (nxt,)] += v
dp = ndp
got = 0
for k, v in dp.iteritems():
if not k[0]&k[-1] : got += v
return got
def xor(n, l):
binrepr = map(int, bin(n)[2:])
binrepr = [0] * (l-len(binrepr)) + binrepr
xor_result = binrepr[0]^(binrepr[1]&binrepr[2])
return int(reduce(lambda x, y : str(x)+str(y), binrepr[1:] + [xor_result]), 2)
def xor_chain(n, l):
got = []
while n not in got:
got.append(n)
n = xor(n, l)
return got
got = []
chains = []
for k in xrange(0, 1<<N):
if k not in got:
nchain = xor_chain(k, N)
got += nchain
chains.append(nchain)
ans = 1
for k in chains:
ans *= circular_logic(len(k))
print ans
p209(6) Ruby:
require 'set'
def g a
a[1, 5] + [a[0] ^ (a[1] & a[2])]
end
def fib(n)
$fib ||= {}
n == 1 ? 1 : n == 2 ? 3 : $fib[n] ||= fib(n - 1) + fib(n - 2)
end
set = Set.new [false, true].product(*([[true, false]] * 5))
count = 1
loop do
orbit = []
break if set.empty?
a = set.first
while not orbit.include?(a)
orbit << a
set.delete(a)
a = g(a)
end
count *= fib(orbit.size)
end
puts count