모바일 오유 바로가기
http://m.todayhumor.co.kr
분류 게시판
베스트
  • 베스트오브베스트
  • 베스트
  • 오늘의베스트
    		•
    유머
  • 유머자료
  • 유머글
    		•
    이야기
  • 자유
  • 고민
  • 연애
  • 결혼생활
  • 좋은글
  • 자랑
  • 공포
  • 멘붕
  • 사이다
  • 꿈
  • 똥
  • 군대
  • 밀리터리
  • 미스터리
  • 술한잔
  • 오늘있잖아요
  • 투표인증
  • 새해
    		•
    이슈
  • 시사
  • 시사아카이브
  • 사회면
  • 사건사고
    		•
    생활
  • 패션
  • 패션착샷
  • 아동패션착샷
  • 뷰티
  • 인테리어
  • DIY
  • 요리
  • 커피&차
  • 육아
  • 법률
  • 동물
  • 책
  • 지식
  • 취업정보
  • 식물
  • 다이어트
  • 의료
  • 영어
  • 맛집
  • 추천사이트
  • 해외직구
    		•
    취미
  • 사진
  • 사진강좌
  • 카메라
  • 만화
  • 애니메이션
  • 포니
  • 자전거
  • 자동차
  • 여행
  • 바이크
  • 민물낚시
  • 바다낚시
  • 장난감
  • 그림판
    		•
    학술
  • 경제
  • 역사
  • 예술
  • 과학
  • 철학
  • 심리학
    		•
    방송연예
  • 연예
  • 음악
  • 음악찾기
  • 악기
  • 음향기기
  • 영화
  • 다큐멘터리
  • 국내드라마
  • 해외드라마
  • 예능
  • 팟케스트
    		•
    방송프로그램
  • 무한도전
  • 더지니어스
  • 개그콘서트
  • 런닝맨
  • 나가수
    		•
    디지털
  • 컴퓨터
  • 프로그래머
  • IT
  • 안티바이러스
  • 애플
  • 안드로이드
  • 스마트폰
  • 윈도우폰
  • 심비안
    		•
    스포츠
  • 스포츠
  • 축구
  • 야구
  • 농구
  • 바둑
    		•
    야구팀
  • 삼성
  • 두산
  • NC
  • 넥센
  • 한화
  • SK
  • 기아
  • 롯데
  • LG
  • KT
  • 메이저리그
  • 일본프로야구리그
    		•
    게임1
  • 플래시게임
  • 게임토론방
  • 엑스박스
  • 플레이스테이션
  • 닌텐도
  • 모바일게임
    		•
    게임2
  • 던전앤파이터
  • 롤
  • 마비노기
  • 마비노기영웅전
  • 하스스톤
  • 히어로즈오브더스톰
  • gta5
  • 디아블로
  • 디아블로2
  • 피파온라인2
  • 피파온라인3
  • 워크래프트
  • 월드오브워크래프트
  • 밀리언아서
  • 월드오브탱크
  • 블레이드앤소울
  • 검은사막
  • 스타크래프트
  • 스타크래프트2
  • 베틀필드3
  • 마인크래프트
  • 데이즈
  • 문명
  • 서든어택
  • 테라
  • 아이온
  • 심시티5
  • 프리스타일풋볼
  • 스페셜포스
  • 사이퍼즈
  • 도타2
  • 메이플스토리1
  • 메이플스토리2
  • 오버워치
  • 오버워치그룹모집
  • 포켓몬고
  • 파이널판타지14
  • 배틀그라운드
    		•
    기타
  • 종교
  • 단어장
  • 자료창고
    		•
    운영
  • 공지사항
  • 오유운영
  • 게시판신청
  • 보류
    		•
    임시게시판
  • 메르스
  • 세월호
  • 원전사고
  • 2016리오올림픽
  • 2018평창올림픽
  • 코로나19
  • 2020도쿄올림픽
    		•
    • 게시판찾기
    • 오유인페이지
    개인차단 상태
    kukbab翁님의
    개인페이지입니다
    가입 : 12-08-14
    방문 : 690회
    닉네임변경 이력
    일반게시판
    베스트게시판
    베스트오브베스트
    댓글목록
    회원차단
    회원차단해제
    		  

    kukbab翁님의 댓글입니다.
    번호 제목 댓글날짜 추천/비공감 삭제
    2 여러 숫자의 최대공약수 [새창] 2014-08-06 19:56:05 0 삭제
    너무 늦은것 같긴 하지만,

    숫자 N개의 gcd를 유클리드호제법으로 한번에 구하는 알고리즘을 만들면 됩니다.
    N개의 수를 array에 모두 넣고, N개에서 최소값 구하고, 각각의 array에 있는 값을 최소값으로 나눈 나머지로 다시 바꾸고 ( 나머지가 0이면, 최소값으로 바꾸기 ), 다 바꾼 후에, 다시 최소값 구해서, 각각의 array에 있는 값을 그 최소값으로 나눈 나머지로 다시 바꾸고, 이렇게 계속 하다가, 최소값과 array에 있는 모든 값이 같게 되면, 그 최소값이 gcd가 됩니다.

    아래는 대충 짠 코드인데, random으로 수를 만들어서 테스트해서 그런지 몰라도, 1000000개도 금방 결과가 나오네요.

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

    long find_min(long * values, int size)
    {
    long min = LLONG_MAX;
    for( int i = 0 ; i < size ; ++i )
    if (min > values[i]) min = values[i];

    return min;
    }

    bool check_gcd(long * values, int size, long min)
    {
    for( int i = 0 ; i < size ; ++i )
    if (min != values[i])
    return false;
    return true;
    }

    long gcd(long * values, int size)
    {
    long gcd_candidate = 0;
    do
    {
    gcd_candidate = find_min(values, size);
    for( int i = 0 ; i < size ; ++i )
    {
    long remain = values[i] % gcd_candidate;
    if (remain == 0)
    values[i] = gcd_candidate;
    else
    values[i] = remain;
    }
    } while(!check_gcd(values,size,gcd_candidate));

    return gcd_candidate;

    }

    int main()
    {
    long values[1000000];
    for( int i = 0 ; i < 1000000 ; ++i )
    {
    values[i] = random();
    }

    printf("gcd is %ldn",gcd(values,1000000));
    }



    [1] [2] [3]

    		 
    단축키 운영진에게 바란다(삭제요청/제안) 운영게 게시판신청 자료창고 보류 개인정보취급방침 청소년보호정책 모바일홈