P1146 硬币翻轉

題目描述

在桌面上有一排硬币，共N枚，每一枚硬币均為正面朝上。現在要把所有的硬币翻轉成反面朝上，規則是每次可翻轉任意N-1枚硬币（正面向上的被翻轉為反面向上，反之亦然）。求一個最短的操作序列（将每次翻轉N-1枚硬币成為一次操作）。

輸入輸出格式

輸入格式：

輸入隻有一行，包含一個自然數N（N為不大于100的偶數）。

輸出格式：

輸出檔案的第一行包含一個整數S，表示最少需要的操作次數。接下來的S行每行分别表示每次操作後桌上硬币的狀态（一行包含N個整數（0或1），表示每個硬币的狀态：0――正面向上，和1――反面向上，不允許出現多餘空格）。

對于有多種操作方案的情況，則隻需字典序最小輸出一種。

輸入輸出樣例

輸入樣例#1：

4      

輸出樣例#1：

4
0111
1100
0001
1111


      

數學方法：第i次翻轉就是翻轉除了第i個硬币以外的所有硬币。

下面給出文字證明：

證明1

定義翻某n-1個為A類操作。

定義B操作，是把所有的硬币全部翻面。

定義C操作，是翻某一個硬币。

題主的問題是若幹次A操作之後能否達到某個狀态，而一個A操作等同于做一次B一次C，注意到B和C操作是可交換的，是以可以了解為先做若幹次數的C操作，然後再做相同次數的B操作。

而做若幹次C操作相當于一個一個硬币地翻，是以第i次翻轉就是翻轉除了第i個硬币以外的所有硬币。

證明2

當然，也可以這樣解釋：做一個很簡單的變換--把每次翻轉5個硬币，分解成兩步：

1、把一個硬币翻轉一次；

2、把所有的硬币翻轉一次

如果p為偶數，那麼上面的第二步實際上被抵消了，是以相當于每次隻做第一步。是以p=6.

如果p是奇數，那麼相當于每次隻做第一步，最後把所有的硬币翻一次面，這等價于隻做奇數次第一步，最後保持所有的硬币仍然是正面向上，這顯然是不能做到的。

綜上，p=6

證明3

要讓所有硬币翻過來，要做的就是每個硬币翻奇數次。

總共六個硬币，每次翻五個。

那麼情況就隻有每個硬币翻一次、三次、五次。

但是每次隻能翻五個，不能多不能少，是以就要求總共翻的次數是5的整倍數。

是以就是每個硬币翻五次。總共翻了5x6=30次

每次翻5個

30/5=6次

答：最少翻六次

1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 int a[10001];
 7 int main()
 8 {
 9     ios::sync_with_stdio(false);
10     int n;
11     cin>>n;
12     cout<<n<<endl;
13     for(int i=1;i<=n;i++)
14     {
15         for(int j=1;j<=n;j++)
16         {
17             if(j!=i)
18             {
19                 a[j]==1?a[j]=0:a[j]=1;
20             }
21         }
22         for(int i=1;i<=n;i++)
23             cout<<a[i];
24         cout<<endl;
25     }
26     return 0;
27 }      

作者：自為風月馬前卒

個人部落格http://attack204.com//

出處：http://zwfymqz.cnblogs.com/

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。