Arithmetic problem | The Triangle
3580 단어 Arithmeticproblemnumberseachgo
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
(Figure 1)
칠
3 : 8
8 : 1 : 0
2 : 7 : 4 : 4
4 : 5 : 2 : 6 : 5
Input:
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
Output
Your program is to write to standard output. The highest sum is written as an integer.
Sample Input:
Triangle
칠
3 : 8
8 : 1 : 0
2 : 7 : 4 : 4
4 : 5 : 2 : 6 : 5
Sample Output: 30
문제 풀이 사고방식: 이 문제는 각 층이 하나의 구성 노선을 선택하여 최대 수치에 도달해야 하기 때문에 동적 기획으로 기존의 데이터 정보를 최대한 활용하여 계산하는 것이 좋은 선택이다.여기서 각 층은 하나의 상태로 점차적으로 점차적으로 증가하는 상태로 문제를 0-2층, 0-3층으로 분해한다...0-(n-1)층의 최대 노선 가치.n-2층의 데이터 이동을 통해 n-1층을 형성하고 n-3층->n-2층, n-4층->n-3층으로 계속 하분한다...주체적으로 보면 비교적 간단한 제목이다.
사고방식 코드는 다음과 같습니다.
int Method(int **n,int len)
{
int res=0;
for(int i=1;i<len;++i)
{
for(int p=0;p<=i;++p)
{
if(p==0) *((int*)n+len*i+p)+= //n[i][p]
*((int*)n+len*(i-1)+p); //n[i-1][p]
else if(p==i) *((int*)n+len*i+p)+=
*((int*)n+len*(i-1)+(p-1)); //n[i-1][p-1]
else *((int*)n+len*i+p)+=
max(*((int*)n+len*(i-1)+(p-1)),
*((int*)n+len*(i-1)+p));
}
}
for(int i=0;i<len;++i)
res=max(res,
*((int*)n+len*(len-1)+i));//n[len-1][i]
return res;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Arithmetic problem | The Triangle제목은 다음과 같습니다. Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a r...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.