c++ - 李白打酒有什么解法

Question

李白打酒

话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：
无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。

这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。 
请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。
注意：通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。

我想到过暴力枚举，但是效果似乎不是很好。这个题用DFS算法解决是很好，但是不理解递归的使用。而且回溯的时候，也不知道这样能不能跑完所有情况。在此求助。

Answer 1

재귀를 사용한 이 질문의 답은 14입니다.

1. 바바바바bbbbbb

2. 바바빠빠빠bbbb

3. 바바바bbbbbb

4. 바바바빠bbbb

5. 바빠bbbbbbbb

6. 바빠빠빠빠

7. 바아바bbbbababb

8. 아빠빠빠bbbb

9. 아빠아빠아bbbb

10. 아바아빠bbbabb

11. 아빠빠빠bbbb

12. 아빠빠빠빠빠

13. 아빠빠빠밥

14. 아바bbbbbabababb

순방향 재귀 외에도 역방향 재귀도 가능합니다.

• 앞으로: (花,店,酒) = (0,0,2)부터 시작하여 (10,5,0)에서 재귀적으로 끝납니다.

• 역방향: (10,5,0), (10,5,0) -> (9,5,1) -> (8,5,2)부터 (0,0,2) 끝까지 역방향으로 작업합니다.

두세 단계를 손으로 추론해 보면 역방향 방법이 더 나을 수도 있다는 것을 알게 될 것입니다. 술의 양이 짝수일 때만, 술의 양을 반으로 줄이려면 매장 이용을 고려해야 합니다. 포워드 푸시 방식의 모든 단계에서는 꽃과 가게라는 두 가지 상황을 고려해야 합니다. 실제 구현에서도 역방향 추론 방법이 순방향 추론 방법보다 훨씬 더 나은 것으로 나타났습니다.

아래 그림은 역방향 메소드의 호출 트리입니다. 원 안의 숫자는 각 추론 단계 이후의 알코올 양, 화살표 문자 P(ub)=호텔, F(lowe)r=꽃입니다. 빨간색 경로는 요구 사항을 충족하는 순서입니다. 총 149개의 재귀 호출이 있습니다(중간 결과는 캐시되며 동일한 형식의 호출은 한 번만 계산됩니다).

아래 그림은 정방향 push 메소드 호출 트리로, 로고는 생략되어 있습니다. 총 1051개의 재귀 호출이 있는데, 대부분 쓸모없는 작업을 수행하고 있습니다.

Answer 2

으아악

저번에 꽃을 만났을 때 와인을 막 마셨기 때문에 마지막 b를 수정했고, 문제는 5a와 9b의 조건부 배열로 단순화되었고, 드디어 와인 한 통이 남았습니다.
질문에는 b-1, wine-1, dfs가 a=0, b=0 및 wine=1이 충족되는지 확인하기 위해 두 가지 상황만 있습니다. is true;
b-1, wine-1, dfs가 다음 레이어에 들어간 후에는 b와 wine의 값을 다시 변경해야 합니다. 그렇지 않으면 다음 명령문의 실행에 영향을 미칩니다. .

Answer 3

그때 우리는 재귀를 사용했습니다.

어쨌든 빈칸 채우기 질문입니다.

Answer 4

이진 열거형의 하위 집합을 사용하여 해결할 수 있습니다.

으아악

위 해결 방법은 Jisuanke의 Blue Bridge Cup 코스에서 발췌한 것입니다. 저는 선원은 아니지만 Jisuanke의 일반 학생입니다. Gmail SF 푸시를 보고 이 문제에 직면했습니다. Blue Bridge Cup의 경우 Jiaji Garanke가 제공하는 코스를 고려해 볼 수도 있습니다. 이 코스는 질문이 많고 세계 상위 27위 안에 드는 교사가 가르칩니다. 위의 링크는 홍보 링크입니다. 등록 후 양측 모두 쿠폰을 받게 됩니다...