C++Builder Programming Forum
C++Builder  |  Delphi  |  FireMonkey  |  C/C++  |  Free Pascal  |  Firebird
볼랜드포럼 BorlandForum
 경고! 게시물 작성자의 사전 허락없는 메일주소 추출행위 절대 금지
C++빌더 포럼
Q & A
FAQ
팁&트릭
강좌/문서
자료실
컴포넌트/라이브러리
메신저 프로젝트
볼랜드포럼 홈
헤드라인 뉴스
IT 뉴스
공지사항
자유게시판
해피 브레이크
공동 프로젝트
구인/구직
회원 장터
건의사항
운영진 게시판
회원 메뉴
북마크
볼랜드포럼 광고 모집

C++빌더 팁&트릭
C++Builder Programming Tip&Tricks
[974] 삼각수열 문제2 - 풀이1
장성호 [nasilso] 8245 읽음    2010-03-26 14:24
아래에
삼각수열 알고리즘 문제를 내었는데...
http://cbuilder.borlandforum.com/impboard/impboard.dll?action=read&db=bcb_tip&no=971

Frigate님께서 답변해주셨네요
http://cbuilder.borlandforum.com/impboard/impboard.dll?action=read&db=bcb_tip&no=972

사실 Frigate님 코드가 잘 이해가 안되지만..

결과는 저랑 같네요..


[풀이1]
예전에 이문제를 접한적이 있었는데..
그때 다음과 같이 풀었었네요

// 삼각수열 배열
int Numbers[] = {
                  64,
                  45, 63,
                  75,  9, 91,
                  15, 72, 84, 86,
                  88,  2, 72, 19, 22,
                  28, 35, 37, 80, 41, 57,
                  10, 60, 31, 25, 20, 24, 92,
                  12, 71, 56, 48,  4, 39, 51,  4,
                  45, 20, 15, 19,  8, 32,  1, 15, 85,
                  27, 66, 98, 14, 22, 58, 14, 20, 73, 18,
                  18, 87, 60, 14, 82, 55, 98,  3, 24, 34, 84,
                   9, 48, 56, 50, 33, 35, 45, 62, 85, 33,  7, 31,
                  44, 91, 55, 47, 38,  6, 52 ,53, 51,  2, 84, 24, 60,
                  30, 53, 87, 92, 96, 95, 59, 02, 13, 32, 11, 85, 74, 37,
                  54, 10, 60, 29, 59, 73, 57, 97, 92, 85, 20, 45, 77, 75, 36,
                  56, 88, 29, 37, 96, 64, 39, 20, 29, 43, 95,  1, 63, 30, 86, 91,
                  23, 86, 39, 97, 41, 42, 67, 52, 82, 34, 66, 58, 87, 73,  8, 73, 43,
                  33, 84,  7, 75, 58, 60, 47, 76, 13, 55, 16, 41, 36, 53, 38, 45, 37, 38,
                  50, 35,  5, 44, 26, 51, 51, 46, 24, 72, 71, 63, 66, 85, 34, 93, 43, 81, 97,
                  70, 32, 76, 47, 46, 59, 55, 57,  1, 67, 43, 83, 72, 21,  1, 77, 17, 35, 44, 22,
                  90, 21, 88, 97, 56, 70, 24, 71, 21, 48,  5, 11, 85, 28, 71, 24, 35, 35, 96, 21, 44,
                  32, 58,  5,  9, 12, 29, 87,  3, 30,  1, 24, 65, 52, 28, 80,  5, 36,  1, 21, 32, 26, 36,
                  25, 21, 85,  1, 21, 87, 47, 56, 55, 99, 86, 31, 79, 12, 27, 11, 63, 17, 65, 62, 36, 36, 21,
                  80, 48, 22, 17, 54, 63, 93, 79, 65, 68, 92, 61,  5, 17, 68, 98, 25, 88, 83, 83, 02, 84, 47, 69,
                  36, 32, 74, 93, 70, 36, 68, 30, 37, 30, 25, 67, 27, 75, 69, 11, 83, 70, 16,  6, 26, 89, 43, 90, 92
                };
//---------------------------------------------------------------------------
int __fastcall GetNum(int col,int row)
{
    if(col>=0 && col<=row)
    {
        int idx=(row*(row+1))/2+col;
 		return Numbers[idx];
    }

    throw Exception("Index Out of Bound");
	return 0 ;

}
//---------------------------------------------------------------------------
void __fastcall GetMaxValue(int iCol,int iRow,int iSum,int &iOutMax)
{
    if(iRow<24)
    {

        GetMaxValue(iCol,iRow+1,iSum+GetNum(iCol,iRow),iOutMax);
        GetMaxValue(iCol+1,iRow+1,iSum+GetNum(iCol+1,iRow),iOutMax);
    }
    else
    {
        if(iOutMax < (iSum+GetNum(iCol,iRow)))iOutMax=iSum+GetNum(iCol,iRow);
        if(iOutMax < (iSum+GetNum(iCol+1,iRow)))iOutMax=iSum+GetNum(iCol+1,iRow);
    }
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
    int iOutMax=0;
    GetMaxValue(0,1,GetNum(0,0),iOutMax);
    ShowMessage("MaxValue="+IntToStr(iOutMax));
}
//---------------------------------------------------------------------------



재귀함수 이용했구요..

그런데 이방식은  2^24승 모두 체크하는 방식입니다.
그래서 시간이 좀 걸리네요 1초정도..


더 좋은 알고리즘은 없을까요?

...

그럼..

+ -

관련 글 리스트
974 삼각수열 문제2 - 풀이1 장성호 8245 2010/03/26
Google
Copyright © 1999-2015, borlandforum.com. All right reserved.