智力题：最少需要多少condom？

这个问题有很长时间的历史了，但是我一直没有去记录它。至于原因嘛，其实蛮复杂的。首先是这个问题的背景很庸俗、涉及的话题不符合广大人民的道德观和价值观，其次这个问题在实际生活中也不太可能发生。虽然有上面一些原因，不过单纯从思维逻辑和方法思路上面还是值得讨论的，最后我决定还是将这个题目的前前后后写下来。供大家当笑料讨论，或者换个方式当智力题（我尝试过将题目换个场景，不过condom这个工具的特性实在不太好阐述清楚，最后放弃了）出出来。

 原始的问题还是很容易解决的，不管是用最一般的穷举法。最后答案是2.在这里我先不解释原因而是将问题拓展成为一般性问题后在做讨论。

 按照一般的解题思路，我们会先在小范围内讨论：

1. 当N=0，不需要；
2. 当N=1,需要一个；
3. 当N=2,需要两个；
4. 当N=3,需要四个；
5. 当N=4,需要六个；
6. 当N=5,需要七个；
7. 当N=6,需要九个；
8. 当N=7,需要十个；
9. 当N=8,需要十二个。

根据上面的数据我们绘制函数图像：

 由图像，我们可以估计到整个变化趋势应该是一个一次线性关系。

现在我们来具体分析一下这个函数关系。

当N=0,1时，毋庸置疑只有配备0、1个；

当N=2时，我们按照平常的思维：N×N=2×2=4个，这样的确太多了。多的原因在哪里呢？以condom的正反两面来算的话，4×2=8个面。而实际上只有2N=4个人,即有4个面的浪费。我们能否将额外的面降低呢？如果按照传统的思维模式，当然是没有办法降低的。我们现在换一个使用方法：套接 。

 利用上面的套接法，我们可以直接发现一个规律：所有的面都是贴在某个使用者外面的。

即：F1一直使用着C2_I,F1一直使用着C1_I,M1一直使用着C1_O,M2一直使用着C2_O，然后通过合理组合来达到目的。

先在将2推广到N：则得到表达式为2N-2

现在我们首先解释为什么是2N-2,然后再给出一个这种思路的下界。

首先是N男N女分别带上一个则共用了N×2=2N个，然后和节水管一样互相接都没有问题了。

这时候我们发现有严重的浪费，有2N面是干净的。能否降低几个呢？现在去掉M1和F1使用的，然后后面的N-1男和N-1女进行交互，最后后面的N-1男用自己的与第一个F1女交互则产生了：Mk >> Ck_O(Mk)-Ck_I(F1) >> F1；让M1直接使用分配给F2...n的condom，则产生了M1 >> C[n+k]_O(M1)-C[n+k]_I(Fk) >> Fk.

最后让M1随便取下一个使用的 C[n+p]_O(M1)-C[n+k]_I(Fk)再到那N-1男中随便取一个Cq_O(Mq)-Cp_I(F1)套接在一起：C[n+p]_O(M1)-C[n+k]_I(Fk)-Cq_O(Mq)-Cp_I(F1)

产生：M1>> C[n+p]_O(M1)-C[n+k]_I(Fk)-Cq_O(Mq)-Cp_I(F1) >> F1

最后我们是降低了两个，使结果变成了2N-2(并且这些condom的面全部使用了，即完全报废)，现在我需要给出利用套接法的这个数据就是下界的证明。

假设还可以去掉一个：则产生了2N-3个condom，抛开M1、M2、F1、F2则另外的N-2男N-2女需要使用：2(N-2)-2=2N-6，还剩下：2N-3-(2n-6)=3。这样我们就发现似乎还有继续减少的余地，不过仔细考虑我们看到有3个分配给前面2男2女用是有余的，但是让他们和后面的N-2男或者N-2女交互的话是不够的。

现在我们得到了下界：2N-2.

即在N大于等于2时，我们得到了2N-2 的最小值。

套接法已经走到了尽头，因为你似乎感觉可以多套几个组合在一起，不过你多套几个和两个相结合其实是一样的，因为干净面永远是干净面无论你前后各套接多少个，如果一个干净的上下都再套干净的没有意义。

在穷途末路的时候，解结构（可以认为是问题体系结构）发生了变化。condom可以翻过来戴 （感谢CM的提醒）。

这样以来我们可以将大小降到：[3N/2]（下取整）.

具体是这样操作的：

 综合上述结论我们得到：

为[3N/2]（下取整）

最后我们总结上述讨论：

get N
if N<=1 then
   return N
endif

if N<=4 then
   return (2*N-2)
endif

if (N mod 2 ==0) then
   return (3*N/2)
else
   return (3*(N-1)/2)
endif

#!/usr/bin/ruby
#Compute the condom
print 'Please press the Number of N:'
n = gets.to_i
res = 0
if n <= 1 then
  res = n
elsif n<=4 then
  res = 2*n-2
else
  res = 3*n/2
end
print "The answer is : #{res}.\n"

思路总结：

1. 思考问题的时候可以先尝试在小范围内穷举出结果，然后利用线性回归等方法估计函数关系
2. 思路很重要，从简单使用到套接到翻转是思维的巨大飞跃
3. 最后具体数据实验后的理论化总结可以让我们更好的来回顾我们的思维习惯，并从中提高自己的思维方式 

希望有更好的解题方法和思路贡献上来。