C\#알고리즘 의 큰 소 가 새끼 소 를 낳 는 문제 의 효율 적 인 해결 방법
2578 단어 C#알고리즘큰 소 는 작은 소 를 낳는다.
갓 태 어 난 송아지 한 마리 가 4 년 뒤에 송아지 한 마 리 를 낳 고 이후 매년 한 마 리 를 낳는다.현재 갓 태 어 난 송아지 한 마리 가 있 는데,20 년 후 에는 모두 몇 마리 가 있 느 냐 고 물 었 다.
생각:
이런 자식 은 손 자 를 낳 고,손 자 는 아들 을 낳 고,자손 의 문 제 는 순환 안에 순환 하 는 내장 순환 이 있어 서,한눈 에 보면 첫 번 째 문제 라 는 것 을 알 수 있다.
그래서 첫 번 째 버 전이 나 왔 다.
public long Compute1(uint years)
{
// 1
long count = 1;
if (years <= 3)
{
return count;
}
int i = 4;
while (i <= years)
{
int subYears = i - 3;
count += Compute1((uint)(subYears));
i++;
}
return (long)count;
}
그러나 이런 순환 하 는 방법 은 cpu 형 을 지치 게 해 야 합 니 다.당신 은 100 년 동안 위의 방법 을 테스트 하 는 것 을 믿 지 않 습 니 다.저 는 한참 을 기 다 렸 지만 결과 가 없습니다.개선 하 세 요.늙 은 소(소 마왕)와 송아지(빨 간 아이,할머니 의 꼬치)는 똑 같은 출산 능력 을 가지 고 있 습 니 다.그들의 출산 곡선 은 같 습 니 다.그래서 소 는 늙 은 소의 출산 경험 을 재 활용 할 수 있 습 니 다.그러면 소 한 마리 가 n 년 째 에 몇 마리 가 공생 하 는 지 반복 적 으로 계산 하 는 문 제 를 해결 할 수 있 습 니 다.나이 가 많 을 때 cpu 의 연산 횟수 를 현저히 낮 출 수 있 습 니 다.다음은 이러한 사고방식 을 바탕 으로 하 는 알고리즘 입 니 다.
Hashtable table = new Hashtable();
public long Compute(uint years)
{
// 1
long count = 1;
if (years <= 3)
{
return count;
}
int i = 4;
while (i <= years)
{
int subYears = i - 3;
if (table.ContainsKey(subYears))
{
count = (long)table[subYears];
}
else
{
count += Compute((uint)(subYears));
}
if (!table.ContainsKey(subYears))
{
table.Add(subYears, count);
}
i++;
}
return (long)count;
}
테스트 프로그램 으로 위의 추론 을 테스트 해 보 세 요.결 과 는 다음 과 같 습 니 다.1)years 를 입력 하 는 것 이 비교적 어 릴 때 첫 번 째 방법 은 시간 이 짧 지만 이들 의 시간 은 기본적으로 하나의 수량 급 에 있다.
2)years 를 입력 하 는 것 이 비교적 클 때 예 를 들 어 40 이상 의 경우 두 번 째 알고리즘 은 첫 번 째 성능 보다 100 이상 이 고 years 를 입력 할 수록 성능 이 현격 하 다.
테스트 결과 캡 처:
20 년
50 년
원본 프로그램 및 테스트 프로그램:http://xiazai.jb51.net/201606/yuanma/HowMoneyCows(jb51.net).rar
이상 이 바로 본문의 전체 내용 입 니 다.여러분 께 참고 가 될 수 있 기 를 바 랍 니 다.여러분 들 도 저 희 를 많이 응원 해 주시 기 바 랍 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
WebView2를 Visual Studio 2017 Express에서 사용할 수 있을 때까지Evergreen .Net Framework SDK 4.8 VisualStudio2017에서 NuGet을 사용하기 때문에 패키지 관리 방법을 packages.config 대신 PackageReference를 사용해야...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.