Rockiswu 2021-08-22 08:05 采纳率: 87.9%
浏览 65
已结题

请给思路:取苹果c++

柜子上有编号1~n的n个苹果,现在有个调皮的小孩把n个苹果从柜子上取下来,然后再放回去,当放回去时要求每个苹果都不能放在原来的位置上,求摆放总方法数;
输入样例:
5
输出样例:
44

  • 写回答

2条回答 默认 最新

  • cupidvenus 2021-08-22 08:50
    关注

    当n=1时,只有1个苹果,不可能错排,故a(n)=0
    当n=2时,1、2只能错排为2、1,故a(n)=1
    考虑n时的错排情况,可从以下两种方法得到n的错排:
    1)前n-1个数已错排,错排数a(n-1),第n个数与前面n-1个数中任何一个数交换均形成错排,因此有(n-1)*a(n-1)种排法
    2)前n-2个数已错排,错排数a(n-2),第n-1和n个数交换,可形成错排,有a(n-2)中排法,交换后,将第n个数再与前面n-2个数中任何一个数交换仍是错排,有(n-2)*a(n-2)种排法,因此共有(n-1)*a(n-2)种排法。此处不能考虑交换后将第n-1个数与前面n-2个数交换,因其排法已包含在情况1)中。
    综合1)、2)可知,当n>=3时,a(n)=(n-1)*a(n-1)+(n-1)*a(n-2),根据这个思路就可以编写程序了。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 8月30日
  • 已采纳回答 8月22日
  • 创建了问题 8月22日

悬赏问题

  • ¥15 哥帮我解决一个报错,看FFastArray 实现原理
  • ¥15 基于ucc28019的pfc电路中芯片一直不工作
  • ¥15 yolov8在3588板子端c++推理报错
  • ¥50 unitywebrequest分段下载导致报错,如何解决?
  • ¥15 错误使用 gretna_GUI_PreprocessInterface>RunBtn_Callback
  • ¥15 WPF如何用Chart绘画出Y轴的左边数据
  • ¥15 pycharm无法查看内置代码
  • ¥15 跑hls xfopencv的例程standalone_hls_axi_example出的错误,csim没问题,c synthesis出的错误
  • ¥15 sqlserver update语句逐行生效
  • ¥20 Windows10系统命令行调用