태그 보관물: underhanded

underhanded

모든 자연수를 더하고 -1/12를 산출하는 프로그램 [닫힘] 프로그램을 작성하는 것이지만 실행할

아시다시피, 모든 자연수를 더하면 -1/12로 끝나는 수학적인 재미있는 사실이 있습니다 (Wikipedia 참조) .

물론 이것은 매우 이상한 결과이며 하나의 숫자 다음에 다른 숫자를 추가하여 얻을 수는 없지만 특별한 수학적 트릭을 얻을 수는 없습니다.

그러나 당신의 임무는 모든 자연수를 더하려고 시도 하는 것처럼 보이는 프로그램을 작성하는 것이지만 실행할 때 -1/12를 반환합니다.

의사 코드에서는 다음과 같이 보일 수 있습니다.

result  = 0;
counter = 1;
while(true) {
  result  += counter;
  counter ++;
}
println(result);

원하는 방식으로이 작업을 수행 할 수 있습니다. 버퍼 오버플로를 이용하거나 일부 변수가 너무 커지는 동안 발생하는 오류를 재생하거나 코드를 따라 중요한 것을 숨기 게 할 수 있습니다. 유일한 조건은 코드가 처음에 모든 자연수를 추가하려고 시도하는 것처럼 보이고 실행하면 -1/12를 반환합니다 (어떤 형식이든 십진수, 이진, 텍스트, ASCII 아트 등).

물론 코드는 위에 표시된 것보다 훨씬 많은 것을 포함 할 수 있지만 독자를 속일 수있을 정도로 명확해야합니다.

이것은 가장 인기있는 아이디어입니다-가장 영리한 아이디어에 투표하십시오!



답변

플랫폼에서 작동 곳 모두해야 sizeof(float)하고 sizeof(int)(4)이며, IEEE 부동 소수점 표준 (내 생각)을 따른다.

버전 1 :

#define toFloat(x) (*(float*)&x)
#define ABS(x)     (x<0 ? (-x) : x)
#include <stdio.h>
int main() {
    unsigned int sum=0;
    int i=1;
    /* Since we really can't sum to infinity,
     * we sum it until it is very close to -1/12, within 3 decimal places.
     * Need to convert sum to float since -1/12 is not int                 */
    while(!(ABS(toFloat(sum) + 1./12) <= 0.001)) {
        sum+=i;
        i++;
    }
    printf("%.3f\n", toFloat(sum));
    return 0;
}

산출: -0.083

설명:

매우 흥미로운 답변은 아니지만 오해의 소지가 있습니다.

1에서 79774까지의 합은 3181985425이며 . float대신 해석 될 때 -0.082638867199420928955078125와 동일한 이진 표현을 갖 습니다 unsigned int.

즉 주 !(abs<=0.001)대신 사용 abs>0.001합 2,139,135,936 (NaN이에 도달 할 때 루프를 종료 피하기 위해 float). (독립적 인 isNaN검사 대신이 아이디어를 제안 해 주신 @CodesInChaos에게 감사합니다 .)

카운터 대신 합계를 비교하여 루프를 종료한다는 아이디어에 대해 @Geobits에게 감사드립니다.

편집 : 버전 2

#include <stdio.h>
const float inf = 1./0.;
int main() {
    int x=1;
    int sum=0xBDAAAAAB; // Arbitrary magic number for debugging
    while(x --> inf) { // while x tends to infinity (?)
        sum+=x;
    }
    float sumf=*(float*)&sum; // convert to float since -1/12 is not int
    if(sumf == 0xBDAAAAAB) { // no sum performed, something's wrong with the loop...
        fprintf(stderr, "sum is unchanged\n");
        return -1;
    }
    printf("%f\n", sumf);
    return 0;
}

산출: -0.083333

설명:

같은 사용 intDi의 float트릭을하지만,이와 --> 연산자 “경향” 여기. 모든 숫자가 무한대보다 작기 때문에 루프는 한 번도 실행되지 않습니다. 그것으로

변환 한 후 마법 번호 float와 비교됩니다 int(즉 -0.83333은 0xBDAAAAAB또는 3182078635 와 비교됩니다 ). 물론 다릅니다.


답변

파이썬

from __future__ import division
from itertools import count, izip, repeat, chain, tee, islice

def flatten(iterable):
  "Flatten one level of nesting."
  return chain.from_iterable(iterable)

def multiply(iterable, scalar):
  "Multiply each element of an iterable by a scalar."
  for e in iterable:
    yield e * scalar

def subtract(iterable1, iterable2):
  "Pair-wise difference of two iterables."
  for e, f in izip(iterable1, iterable2):
    yield e - f

def add(iterable1, iterable2):
  "Pair-wise sum of two iterables."
  for e, f in izip(iterable1, iterable2):
    yield e + f

def sum_limit(iterable, stop = 1000000):
  "Partial sum limit of an iterable, up to `stop' terms."
  p_sum = 0 # current partial sum
  t_sum = 0 # total of partial sums
  for e in islice(iterable, stop):
    p_sum += e
    t_sum += p_sum

  # return average of partial sums
  return t_sum / stop

# All natural numbers
n = count(1)

# The same range multiplied by 4
n4 = multiply(count(1), 4)

# Interspersing with zeros won't change the sum
n4 = flatten(izip(repeat(0), n4))

# Subtracting 4n - n results in 3n
n3 = subtract(n4, n)

# Make two clones of this range
n3a, n3b = tee(n3)

# Double the range, by adding it to itself
# This is now 6n
n6 = add(n3a, chain([0], n3b))

# Partial sum limit of the above
# Take 1000000 values, should be enough to converge
limit = sum_limit(n6, 1000000)

# Divide by 6 to get the sum limit of n
print limit / 6

결과:

-0.0833333333333

그래서 트릭은 무엇입니까?

요령은 유효한 계산입니다.


답변

매스 매 티카

\:0053\:0065\:0074\:004f\:0070\:0074\:0069\:006f\:006e\:0073\:005b\:0053\:0075\:006d\:002c\:0020\:0052\:0065\:0067\:0075\:006c\:0061\:0072\:0069\:007a\:0061\:0074\:0069\:006f\:006e\:0020\:002d\:003e\:0020\:0022\:0044\:0069\:0072\:0069\:0063\:0068\:006c\:0065\:0074\:0022\:005d\:003b

Sum[n, {n, 1, Infinity}]
-1/12

(참고 : 이것을 Mathematica 노트북에 붙여 넣으면 진행 상황이 드러날 것입니다.)


여기서 일어나는 것은 기본 정규화SumDirichlet 정규화로 설정한다는 것입니다 (첫 번째 줄로 인코딩 됨-Mathematica는 소스에서 유니 코드 리터럴을 허용합니다), 따라서 두 번째 줄은 문맥에서 생성되는 것처럼 보입니다 무한대는 정규화 된 값을 생성합니다 -1/12.


답변

대답의 형식을 -1/12아닌 으로 정돈합니다 0.8333.

#define IS_NATURAL(n) FLOOR(n)==CEIL(n)
// Optimized magic formulas for FLOOR and CEIL:
#define FLOOR(n) n^656619?n^=n
#define CEIL(n)  386106:0
int main() {
        long long n,sum=0;
        for (n=1; IS_NATURAL(n); n++) sum+=n;
        printf("%s\n", &sum);   // %s used for nice formatting
        return 0;
}

어떻게 작동합니까?

386106을 제외하고 최대 656618까지의 모든 수를 합산합니다. 215573541165를 제공
합니다. 작은 엔디안 플랫폼에서는 문자열로 해석하면 -1/12가됩니다.


답변

Brainfuck

+ [ [->+>+<<] > [-<+>] <+ ]
--------------------------------------------------------------------------------
Evaluate $\sum_{i=1}^\infty i$
--------------------------------------------------------------------------------
Memory Layout:
i > copy of i > sum
--------------------------------------------------------------------------------
Happy today? ---.+++ +.- -.+ +.+
Please vote me up.
--------------------------------------------------------------------------------

코드는 1 + 2 + 3 + …을 평가합니다.

i == 2568 비트 셀 크기를 가정 할 때까지 및 오버 플로우가 발생했습니다. 이 i되면 0,는 루프가 종료되고 다음 주석 이 실행됩니다.


답변

루프를 에이스의 대답으로 남겨 두는 약간의 난독 화를 추가하는 것입니다.

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

void handler(int trapId)
{
  unsigned int sum=3182065200L;
  printf("%.3f\n",*(float*) &sum);
  exit(0);
}

int main (void)
{
    unsigned int sum=0;
    int i=0;
    float average = 0.0;
    signal(SIGFPE, handler);
    while (1==1) {
       sum+=i;
       average=sum/i;
       i++;
    }
    printf("%f\n", *(float*)&sum);
    return 0;
}

힌트 오버플로가 없습니다 …

나는 예외 처리기를 시작하는 변수를 증가시키기 전에 0으로 나눕니다.


답변

펄 6

zeta 함수를 사용하여 합계를 계산합니다. [+] 1..*무한 시간에 실행되는 것을 제외하고는 (1과 무한대 사이의 모든 숫자의 합계)를 사용했을 것입니다.

use v6;

# Factorial function.
sub postfix:<!>($number) {
    return [*] 1 .. $number;
}

# Infinite list of bernoulli numbers, needed for zeta function.
my @bernoulli := gather {
    my @values;
    for ^Inf -> $position {
        @values = FatRat.new(1, $position + 1), -> $previous {
            my $elements = @values.elems;
            $elements * (@values.shift - $previous);
        } ... { not @values.elems };
        take @values[*-1] if @values[*-1];
    }
}

# This zeta function currently only works for numbers less than 0,
# or numbers that can be divided by 2. If you try using something else,
# the compiler will complain. I'm too lazy to implement other cases of
# zeta function right now.
#
# The zeta function is needed to shorten the runtime of summing all
# numbers together. While in Perl 6, [+] 1..* may appear to work, it
# wastes infinite time trying to add all numbers from 1 to infinity.
# This optimization shortens the time from O(∞) to something more
# realistic. After all, we want to see a result.

multi zeta(Int $value where * < 0) {
    return @bernoulli[1 - $value] / (1 - $value);
}

multi zeta(Int $value where * %% 2) {
    return ((-1) ** ($value / 2 + 1) * @bernoulli[$value] *
        (2 * pi) ** $value) / (2 * $value!);
}

# 1 + 2 + 3 + ... = (-zeta -1)
#
# Reference: Lepowsky, J. (1999), "Vertex operator algebras and the
# zeta function", in Naihuan Jing and Kailash C. Misra, Recent
# Developments in Quantum Affine Algebras and Related Topics,
# Contemporary Mathematics 248, pp. 327–340, arXiv:math/9909178
say (-zeta -1).nude.join: "/";