1부터 100까지 더하는 합리(!)적인 알고리즘

wputer의 이미지

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
 
#define SUM_MAX 100
 
 
int main(int argc, char *argv[]) {
        int n, i, sum, checksum;
        int check[SUM_MAX];
 
 
        n=i=sum=checksum=0;
 
 
        for(i=0; i<SUM_MAX; i++) {
                check[i] = i+1;
        }
 
        sleep(1);
        srand(time(NULL)) ;
 
 
        while(1) {
                n = rand()%SUM_MAX + 1;
 
 
                if((n > 0) && (n < SUM_MAX+1)) {
                        if(check[n-1]>0)
                                sum += n;
                        check[n-1] = 0;
 
 
                        checksum = 0;
                        for(i=0; i<SUM_MAX; i++) {
                                checksum += check[i];
                        }
                        if(checksum==0)
                                break;
                }
        }
 
 
        printf("result : %d\n",sum);
 
 
        return 0;
}

모 커뮤니티를 가보니까 1에서 100까지 더하는 프로그램을 꽤 여러 버전으로 해놨더라구요
거기 올리려고 짜본건데
왠지 짜놓고 보니 뿌듯해서 올려봅니다

이정도면 꽤 합리(!)적이죠? ^_^

익명 사용자의 이미지

1부터 n까지 더하는 알고리즘
고등학교 책에 나옴

sum = n(n+1) / 2

끝. 간단하죠?

익명 사용자의 이미지

한줄짜리
main() { int n = 100; printf("%d\n", n * (n + 1) / 2); }

shint의 이미지

ㅇ_ㅇ''' 하나의 예술작품이군요.

----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.

매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.

각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com

MasterQ의 이미지

몇배나 돌까 궁금해서 돌려봤습니다. 한 300-600번정도 도는군요. 생각보다 너무 빨리 끝나서 약간 실망했습니다.

--덧--
원 프로그램의 의도를 진지하게 받아들이시는 분들이 계신것 같네요. :)

divetou의 이미지


지나가다 궁금한 마음에 댓글 남깁니다.

합리적이라는 말의 의미가 궁금하네요. ^^;

빠른게 합리적이라면..
존재하는 공식 (closed form)으로 계산하는게 더 합리적이지 않을까요? :)

==============================
꿈꾸는소년

익명 사용자의 이미지

딱봐도 반어법으로 쓴거같은데 ㅎㅎ 오해하시는분이 많으신듯

본문에는 느낌표 까지 ㅎㅎ

wputer의 이미지

설마요 당연히 반어법입니다

divetou의 이미지

ㅎㅎ 저도 왠지 반어법인것도 같았지만,
다른 관점의 합리적이라는게 있나 궁금했습니다. ^^; ㅎㅎ

뭔가 새로운 방법인가 했거든요. (제가 모르는게 많다보니.. T.T)

==============================
꿈꾸는소년

지리즈의 이미지

저것 보다 더 합리(!)적인 방법이 있을까?

너무나도 합리적(!)임에도 불구하고 군더더기가 하나도 없네요.

There is no spoon. Neo from the Matrix 1999.

Fe.head의 이미지

// sum = n(n+1) / 2;
sum = (n*(n+1)) >> 1;

컴파일러가 최적화하겠지만 ㅎㅎ

고작 블로킹 하나, 고작 25점 중에 1점, 고작 부활동
"만약 그 순간이 온다면 그때가 네가 배구에 빠지는 순간이야"

snowall의 이미지

wputer님이 쓴 코드를 Fe.head님의 코드처럼 최적화 할 수 있는 컴파일러가 있을까요? (언어에 상관 없이...)

사람 빼고요. -_-;

피할 수 있을때 즐겨라! http://melotopia.net/b

카二리의 이미지

1부터 100까지 더하는데 왜 그런 비효율적이고 느리게 계산들을 하심? 시키지도 않은 N까지 더하시다니!

return 5050;

이것보다 더 빠를순 없을것 같네요.

새 생각 :)

익명 사용자의 이미지

ㅋㅋㅋㅋ 그렇네요^^

익명 사용자의 이미지

#define SUM(n) (n * (n + 1) / 2)
 
int main()
{
    return SUM(100);
}

매크로 이용하여 return 5050; 이랑 속도 동일

ipes4579의 이미지

return 5050;

return (100 * (100 + 1) / 2) 

가 속도가 동일하다구요?

대충만 봐도 1000배는 느리겠는데요?

오리가날지못해우물에빠진날의 이미지

#define SUM(n) (n * (n + 1) / 2)
return SUM(100);

위의것과

return (100 * (100 + 1) / 2)

이것은 분명 다릅니다.

paranpi7의 이미지

프리프로세스 를 거치게 되면
메크로 치환으로 인해 둘은 같은 값으로 바뀌게 되죠 .
gcc 가 설치된 경우 CC -E 나 CPP 로 확인 해보세요.

오리가날지못해우물에빠진날의 이미지

제가 잠시 착각했었네요.

swirlpotato의 이미지

컴파일러 최적화때문에 같은 결과가 나옵니다.

stypr의 이미지

Constant folding 에 해당됩니다.

익명 사용자의 이미지

$ diff 1/sum.c 2/sum.c
1,6c1,4
< #define SUM(n) (n * (n + 1) / 2)
<  
<  int main()
<  {
<          return SUM(100);
<  }
---
> int main()
> {
>     return 5050;
> }
$ make 1/sum ; make 2/sum; diff 1/sum 2/sum
cc     1/sum.c   -o 1/sum
cc     2/sum.c   -o 2/sum

동일한 binary 가 생성됨을 확인하였습니다.

ipes4579의 이미지

흠.. 그렇네요. 생성된 바이너리를 보니 같네요.

최적화 옵션을 주지 않았는데도 같은 바이너리가 생성된다니, 컴파일러를 똑똑하다고 해야할지 건방지다고(?) 해야할지.

어쨌든 새로운거 알았네요. 감사합니다.

세벌의 이미지

1등 놓쳤네요. 제가 그렇게 쓰려고 했는데...

ipes4579의 이미지

srand(time(NULL))이 생각보다 그렇게 잘 섞이지 않습니다.

저 프로시저는 1초안에 끝나니 아마 계속 똑같은 시드를 유지하고 있을 겁니다.

srand를 좀더 합리적으로 활용할 수 있게끔 생각해오세요.

예를 들면.. Sleep(1000); 을 준다던가 하는 식으로 합리적으로 생각해오세요.

wputer의 이미지

조언 감사합니다.
저도 여러번 돌렸는데 초단위로 끊기다보니
같은 결과가 자주 나오더군요..
조언대로 srand전이나 후에 1초 슬립을 주면 좋겠군요.
ㅎㅎ 감사합니다 바로 수정해 넣을꼐여

xyhan의 이미지

return 101*50;

============================================================

선한 인간이냐 악한 인간이냐는 그사람의 의지에 달렸다. -에픽테토스-
의지 노력 기다림은 성공의 주춧돌이다. -파스퇴르-

============================================================

xyhan의 이미지

--

============================================================

선한 인간이냐 악한 인간이냐는 그사람의 의지에 달렸다. -에픽테토스-
의지 노력 기다림은 성공의 주춧돌이다. -파스퇴르-

============================================================

익명 사용자의 이미지

| ?- [user].
compiling user for byte code...
sum(0, 0).
sum(X, S) :- X > 0, X1 is X - 1, sum(X1, S1), S is X + S1.

user compiled, 3 lines read - 791 bytes written, 32544 ms

(2 ms) yes
| ?- sum(10, S).

S = 55 ? a

no
| ?- sum(100, S).

S = 5050 ? a

no