Question

求一道C++题目的思路

问题如下：

有趣的数（intresting.pas/.c/.cpp）
问题描述：
某一个n（3<=n<=100）位数的数只有1、2和3组成，其中每个数至少出现一次，并且要求每个1要在2之前，每个2要在3之前，请编程求出这样的数有多少个。
输入格式：
一行一个整数n，表示这个数的位数。
输出格式：
一行一个整数，表示满足要求的数的个数。
样例输入：
3
样例输出：
1

求解这位道题的思路是什么？不要代码

Answer 1

（注：C（m,n）表示数学上的“组合”：m选n）
相当于这样的问题：把n（位数）个元素，分为m1、m2、m3三个组，满足：
m1,m2,m3>=1;
m1+m2+m3=n
用10位数举例：
用排列组合法：1【11|22|3333】3这是一种排法。根据题意，最左边必然为1，最右必然为3。只考虑括号【】中间的8个位置。|当做隔板。用插空法：【,0,0,0,0,0,0,0,0,】一共可以有9个空，插2个隔板。隔板左边是1（括号【】内可以没有1，因为外边已经有一个），两个中间是2，右边是3

因此最后答案是：C(n-1，2)

Answer 2

迭代判断可以做，但是效率不好，尤其到n=100的时候，迭代的次数太多。
应该是使用算法来进行计算。

按描述比较符合组合的方法，5个位置取3个不同的东西放入，不考虑排序。
在组合里，11233和33211，12331是一样的，算一种
应该还有一些具体的细节需要考虑一下.......

追问

cin>>n;
cout<<(n-2)*(n-1)/2;
这个算法是什么意思呢？

追答

简化下：
有N个位置，1,2,3一共3个数，并且至少存在一个。
那么N里有3个位已经分别被1,2,3占用了，还剩下N-3个位置，每个位置可以放3种数。

一共有3的N次方种方法，然后把重复的部分去掉。
比如12 和 21是一样的

追问

(n-2)*(n-1)/2代表的是什么呢？

Answer 3

考虑一下用迭代呀

追问

但是怎么实现呢？最简单的可以一个输入一个输出就能解决