무한한 수준을 가질 수 있는 트리, 노드가 가질 수 있는 자식의 수를 저장할 변수 자식, 경로와 관련된 가중치를 저장할 변수 가중치 및 경로와 작업을 저장할 변수 경로가 주어집니다. 가중치가 X와 같고 주어진 가중치를 가진 최소한 하나의 간선이 있어야 하는 경로의 수를 계산합니다.
예
입력 - int 자식 =4, 가중치 =4, 경로 =4;
출력 - 가중치가 정확히 X이고 가중치 M의 모서리가 하나 이상 있는 경로 수는 다음과 같습니다. 1
설명 - 4개의 경로와 연결된 4개의 자식이 있고 경로와 관련된 가중치가 4인 노드가 주어졌기 때문입니다. 따라서 가중치가 4인 경로는 하나만 있을 수 있음을 알 수 있습니다. 즉 1 - 4이므로 개수는 1입니다.
입력 - int 자식 =3, 가중치 =2, 경로 =4;
출력 - 가중치가 정확히 X이고 가중치 M의 모서리가 하나 이상 있는 경로 수는 다음과 같습니다. 4
설명 - 4개의 경로와 연결된 3개의 자식이 있고 경로와 관련된 가중치가 2인 노드가 제공됩니다. 따라서 가중치가 2인 4개의 경로(예:1-1, 1-2, 2-1 및 2-1)가 있을 수 있으므로 개수는 4입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
- 변수의 자식, 가중치, 경로 각각에 각 경로와 연관된 자식, 경로 및 가중치의 총계를 입력합니다.
- 주어진 크기의 배열을 선언합니다.
- 배열의 크기까지 i에서 0까지 FOR 루프를 시작합니다. 루프 내에서 j가 2보다 작을 때까지 j에서 0까지 다른 루프 FOR를 시작한 다음 arr[i][j]를 -1로 설정합니다.
- 이제 path, 0, weight, child 및 arr을 함수의 인수로 전달하여 total_weight() 함수를 호출합니다.
- 함수 내부
- 결과를 저장할 임시 변수 개수를 선언합니다.
- IF 경로가 0보다 작은지 확인한 다음 0을 반환합니다.
- IF 경로가 0인지 확인한 다음 i를 반환합니다.
- arr[경로][i]가 1과 같지 않은지 확인한 다음 arr[경로][i]를 반환합니다.
- 자식까지 j에서 1까지 FOR 루프를 시작합니다. 루프 내에서 path-j, 1, weight, child 및 arr을 함수에 인수로 전달하여 total_weight() 함수에 대한 재귀 호출로 IF j가 set count보다 가중치인지 확인합니다.
- 그렇지 않으면 path-j, i, weight, child 및 arr을 함수에 인수로 전달하여 total_weight() 함수에 대한 재귀 호출로 count를 설정합니다.
- arr[경로][i]를 개수로 설정하고
- 반환[경로][i]
- 결과를 인쇄합니다.
예
#include <bits/stdc++.h>
using namespace std;
#define size 4
#define col 4
int total_weight(int path, int i, int weight, int child, int arr[size + 1][col]) {
int count = 0;
if (path < 0) {
return 0;
}
if (path == 0) {
return i;
}
if (arr[path][i] != -1) {
return arr[path][i];
}
for (int j = 1; j <= child; j++) {
if (j == weight) {
count += total_weight(path - j, 1, weight, child, arr);
} else {
count += total_weight(path - j, i, weight, child, arr);
}
}
arr[path][i] = count;
return arr[path][i];
}
int main() {
int child = 4, weight = 4, path = 4;
int arr[size + 1][col];
for (int i = 0; i <= size; i++) {
for (int j = 0; j < 2; j++) {
arr[i][j] = -1;
}
}
cout << "Count of number of paths whose weight is exactly X and has at-least one edge of weight M are: " << total_weight(path, 0, weight, child, arr);
} 위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
출력
Count of number of paths whose weight is exactly X and has at-least one edge of weight M are: 1