알고리즘 기초 동적계획 연습문제 레포트

*길*
개인인증판매자스토어
최초 등록일
2015.07.13
최종 저작일
2015.04
12페이지/한글파일 한컴오피스
가격 1,000원 할인쿠폰받기
다운로드
장바구니
퀴즈OX 이벤트

소개글

출판사 : 홍릉과학출판사
저자 : Richard Neapolitan
역자 : 도경구

연습문제 레포트 입니다.
윈도우 7 , visual studio 2013

목차

없음

본문내용

2 . 등식 (3.1)을 기초로 하여 이항계수문제(알고리즘 3.1)을 푸는 분할정복 알고리즘은 nCk 를 구하는데 2*nCk – 1 개의 항을 계산함을 n에 관한 귀납법으로 증명하시오.
먼저 n = 1 인 경우 1Ck = 2 * 1Ck – 1 임 을 증명하면 된다.
1Ck 인 경우 k는 0 또는 1 인데 두 가지 경우 다 1 을 나타내므로 위에 등식은
1 = 2 – 1 이 되므로 성립한다.
다음으로 nCk 에 대하여 2*nCk –1 개의 항을 계산 한다고 가정 하였으므로
(n+1)Ck 에 대하여 2*(n+1)Ck –1 이 성립 되는지 알아보면 된다.
여기서 이항계수 성질 중에 nCk = (n-1)C(k-1) + (n-1)Ck 라는 식이 성립 되므로
우리는 nC(k-1) 을 구하기 위한 항의 갯수와 + nCk 을 구하기 위한 항의 갯수에 두개의 항을 더하기 위한 항의 갯수 1 을 더하는 횟수를 구하면 된다. 그럼 여기에 가정을 대입하면
nC(k-1) = 2 * nC(k-1) - 1 , nCk = 2 * nCk - 1 이므로
(n+1)Ck = 2 * nC(k-1) -1 + 2 * nCk –1 +1 이 성립되어야 한다.

참고 자료

없음

자료후기(3)

*길*
판매자 유형Silver개인인증

주의사항

저작권 자료의 정보 및 내용의 진실성에 대하여 해피캠퍼스는 보증하지 않으며, 해당 정보 및 게시물 저작권과 기타 법적 책임은 자료 등록자에게 있습니다.
자료 및 게시물 내용의 불법적 이용, 무단 전재∙배포는 금지되어 있습니다.
저작권침해, 명예훼손 등 분쟁 요소 발견 시 고객센터의 저작권침해 신고센터를 이용해 주시기 바랍니다.
환불정책

해피캠퍼스는 구매자와 판매자 모두가 만족하는 서비스가 되도록 노력하고 있으며, 아래의 4가지 자료환불 조건을 꼭 확인해주시기 바랍니다.

파일오류 중복자료 저작권 없음 설명과 실제 내용 불일치
파일의 다운로드가 제대로 되지 않거나 파일형식에 맞는 프로그램으로 정상 작동하지 않는 경우 다른 자료와 70% 이상 내용이 일치하는 경우 (중복임을 확인할 수 있는 근거 필요함) 인터넷의 다른 사이트, 연구기관, 학교, 서적 등의 자료를 도용한 경우 자료의 설명과 실제 자료의 내용이 일치하지 않는 경우

찾던 자료가 아닌가요?아래 자료들 중 찾던 자료가 있는지 확인해보세요

더보기
우수 콘텐츠 서비스 품질인증 획득
최근 본 자료더보기
알고리즘 기초 동적계획 연습문제 레포트