(求助)觉得dfs有问题
查看原帖
(求助)觉得dfs有问题
557408
Tony_rao楼主2022/7/3 10:01

用这个代码过了,但是觉得有问题

#include<bits/stdc++.h>
using namespace  std;

int n , num[50] = {1} ,Count = 0;

void print(int k)
{
  printf("%d=%d" ,n ,num[1]);
  for(int i=2; i<k; i++)
    printf("+%d",num[i]);
  printf("\n");
  ++Count;
}
void dfs(int k , int remain)
{
  if(remain ==0 && k>2)
    print(k);
  else
    for(int i=num[k-1]; i<=remain; i++)
    {
      cout << "num[k-1] " << num[k-1] << endl;
      cout << "i " << i << endl;
      cout << "num[k] " << num[k] << endl;
      cout << "k " << k << endl;
      cout << "remain " << remain << endl;
      num[k] = i;
      remain -= i;
      dfs(k+1,remain);
      remain+=i;
    }
}
int main()
{
  cin >> n;
  dfs(1,n);
  printf("%d\n",Count);
  return 0;
}
4
num[k-1] 1
i 1
num[k] 0
k 1
remain 4
num[k-1] 1
i 1
num[k] 0
k 2
remain 3
num[k-1] 1
i 1
num[k] 0
k 3
remain 2
num[k-1] 1
i 1
num[k] 0
k 4
remain 1
4=1+1+1+1
num[k-1] 1//源代码中说了i = num[k-1]; 
i 2//但是这里的i直接赋值为2了,但是num[k-1]是等于1啊!!
num[k] 1
k 3
remain 2
4=1+1+2
num[k-1] 1
i 2
num[k] 1
k 2
remain 3
num[k-1] 1
i 3
num[k] 2
k 2
remain 3
4=1+3
num[k-1] 1
i 2
num[k] 1
k 1
remain 4
num[k-1] 2
i 2
num[k] 3
k 2
remain 2
4=2+2
num[k-1] 1
i 3
num[k] 2
k 1
remain 4
num[k-1] 1
i 4
num[k] 3
k 1
remain 4
4

2022/7/3 10:01
加载中...