目錄

• 引言
• 具體解法
• • • 問題描述
    • 輸入
    • 輸出
    • 樣例輸入
    • 樣例輸出
    • 解題思路
    • 代碼實現
• 總結

引言

???????高中物理有一個十分經典的問題，即小球碰撞問題。將這個物理問題簡化，不考慮能量損耗，且假設每個小球的速度大小與質量都一致，就成為一個經典的算法問題，即給定若干小球的初始位置與速度矢量，計算一段時間后各小球的位置與運動情況。
???????這是一個很經典的問題，也已經有了許多C語言的大佬對此題給出了非常巧妙的算法。筆者作為一個C語言新手，還很難超越前人，創造出更巧妙的算法，但想在此給出一種較為繁復甚至有些笨拙，卻能通過模擬這個運動過程最終給出答案的暴力解題法。希望我的解法能作為對這個問題算法一個微不足道的補充，也希望能為和我一樣的初學者帶來啟發。同時，筆者也真誠地期待看到此篇文章的前輩們不吝賜教，對我的算法進行批評指正。

具體解法

本問題的核心在于運動過程中小球的相遇，以及碰撞之后方向的改變，而筆者的代碼原本是為另一道與此小球碰撞本質相同的問題書寫的。為了方便，我將直接以這道與小球碰撞本質相同的問題為例，對此算法進行解釋。

問題描述

???????長度為 L 的直跑道上有 n 個同學，每個同學只會朝南或北兩個方向走，速度都為 1 米每秒 。當兩個同學相遇時，兩個同學將同時轉向（轉身時間忽略不計）。現給出每個同學的初始位置和運動方向，計算 T 秒后每個同學的位置。（說明：這里指的位置由同學距離跑道北端起點的距離表示，位于最北端的同學位置是 0 ，位于最南端的同學位置是 L 。）

輸入

???????第一行為三個用空格分隔的正整數 L , n , T ( 1 ≤ n ≤ L ≤ e4 , 0 ≤ T ≤ e4 )。
???????之后 n 行，每行一個正整數 x (0 ≤ x ≤ L )，表示同學到跑道最北端起點的距離，和一個字母 c 表示初始朝向。 c 只會為 N 或 S ， N 表示朝北， S 表示朝南。 保證每位同學的初始位置不同。

輸出

???????輸出 n 行，按輸入順序輸出每位同學的位置和朝向，中間用一個空格隔開。對于在第 T 秒之前已經走出 TD 線的同學，輸出 Finished 。（說明：朝向用字符表示，N 表示朝北，S 表示朝南，Turning 表示正在轉身。)

樣例輸入

10 4 1 1 S 5 S 3 N 10 S

樣例輸出

2 Turning 6 S 2 Turning Finished

解題思路

???????在這個運動過程中，重要因素包括各同學的初始位置和每個同學的速度矢量，其實本題給出數據輸入格式時已經將這些這些因素數據化。如果我們把每個同學看做一個對象，將其位置與速度矢量（由于這里速度大小恒為 1 ，因此主要是朝向），賦給這個對象即可。為此，我們可以定義兩個數組（字符數組），分別用來記錄每位同學的位置和朝向，通過數組（字符數組）的下標實現與每位同學的一一對應。此外，還需定義一個數組表示跑道（相當于數軸）的各個位置坐標。以便判斷運動中相遇的情況。
???????接下來，就要通過程序運算模擬每位同學的運動，這可以通過對與每位同學一一對應的位置和朝向數組進行操作來實現。但在考慮運動過程中相遇的情況時，如果選 1 為時間間隔，那么相遇就可能發生在每一時間間隔的中間或者末尾。對于發生在中間的相遇，可以直接互換二者的朝向，位置不變；而當相遇發生在，時間間隔末尾時，二者在這一瞬間會“重疊”。這時，一個表示各跑道位置坐標的數組已經不夠，還需要再定義一個相同的數組以儲存“重疊”的對象。
???????在運動結束的瞬間，仍可能發生相遇轉身的情況，因此最后還應再對可能的相遇情況進行一次處理。

代碼實現

#include<stdio.h>int Position[10100]; //以數組Position記錄每位同學的位置，數組的下標即同學的編號； int Record[10100],AnotherRecord[10100]; //以數組Record記錄跑道上每個位置是否有同學，以跑道為x軸，數組的下標即不同位置的坐標；數組AnotherRecord用于位置重疊時的記錄； int op[10100]; //以數組op標記對應同學所作的操作——繼續前進或轉身，數組的下標即同學的編號； char Der[10100]; //定義字符數組Der，記錄每位同學的前進方向，數組的下標即同學的編號； int L,n,T;void ChangeDirection(int a,int b) {char carrier;carrier=Der[a];Der[a]=Der[b];Der[b]=carrier; }int main() {int i;int t; //記錄跑道上同學的運動時間；scanf("%d%d%d",&L,&n,&T);for(i=1; i<=n; i++)scanf("%d %c",&Position[i],&Der[i]); //錄入每位同學的初始位置與運動方向；for(t=1; t<=T; t++) //t的增加代表時間的演進；{for(i=0; i<10010; i++) //初始化數組；{Record[i]=-1;op[i]=0;AnotherRecord[i]=-1;}for(i=1; i<=n; i++){if(Position[i]>=0&&Position[i]<=L){if(Record[Position[i]]==-1)Record[Position[i]]=i; //數組Record中對應的數字為-1代表該位置為空，可以直接占據這個位置，并將Record中該點對應的值賦為占據這個點的同學的編號；else{ChangeDirection(i,Record[Position[i]]);AnotherRecord[Position[i]]=i; //若該位置有人的話，則兩者交換前進方向，位置坐標不變}}else{Position[i]=-1;Der[i]='F'; //以'F'表示該同學已走出跑道，走出跑道的同學位置統一標記為-1；}}for(i=1; i<=L; i++) //遍歷一次每位同學的運動情況，檢查本次運動中是否會有相遇的情況；{if(Position[i]>0){/*注：這里在判斷相遇時，由于部分位置可能存在重疊，因此要檢查運動的兩端是否存在重疊，以及重疊的兩個人各自的相遇情況，即4種情況*/if(Record[Position[i]-1]!=-1&&Record[Position[i]]!=-1&&Der[Record[Position[i]-1]]=='S'&&Der[Record[Position[i]]]=='N'&&op[Record[Position[i]-1]]==0&&op[Record[Position[i]]]==0){ChangeDirection(Record[Position[i]-1],Record[Position[i]]);op[Record[Position[i]-1]]=1;op[Record[Position[i]]]=1;}else if(AnotherRecord[Position[i]-1]!=-1&&AnotherRecord[Position[i]]!=-1&&Der[AnotherRecord[Position[i]-1]]=='S'&&Der[AnotherRecord[Position[i]]]=='N'&&op[AnotherRecord[Position[i]-1]]==0&&op[AnotherRecord[Position[i]]]==0){ChangeDirection(AnotherRecord[Position[i]-1],AnotherRecord[Position[i]]);op[AnotherRecord[Position[i]-1]]=1;op[AnotherRecord[Position[i]]]=1;}else if(AnotherRecord[Position[i]-1]!=-1&&Record[Position[i]]!=-1&&Der[AnotherRecord[Position[i]-1]]=='S'&&Der[Record[Position[i]]]=='N'&&op[AnotherRecord[Position[i]-1]]==0&&op[Record[Position[i]]]==0){ChangeDirection(AnotherRecord[Position[i]-1],Record[Position[i]]);op[AnotherRecord[Position[i]-1]]=1;op[Record[Position[i]]]=1;}else if(Record[Position[i]-1]!=-1&&AnotherRecord[Position[i]]!=-1&&Der[Record[Position[i]-1]]=='S'&&Der[AnotherRecord[Position[i]]]=='N'&&op[Record[Position[i]-1]]==0&&op[AnotherRecord[Position[i]]]==0){ChangeDirection(Record[Position[i]-1],AnotherRecord[Position[i]]);op[Record[Position[i]-1]]=1;op[AnotherRecord[Position[i]]]=1;}}}for(i=1; i<=n; i++){if(Der[i]=='S'&&op[i]==0)Position[i]=Position[i]+1;else if(Der[i]=='N'&&op[i]==0)Position[i]=Position[i]-1;}//數組op對應的值為0時表示繼續前進，值為1時表示本次轉身，不前進；}/*最后一秒末可能存在兩位同學正好走到同一位置的情況，因此要再判斷一次*/for(i=0; i<10010; i++)Record[i]=-1;for(i=1; i<=n; i++){if(Position[i]>=0&&Position[i]<=L){if(Record[Position[i]]==-1)Record[Position[i]]=i;else if(Record[Position[i]]!=-1){Der[i]='T';Der[Record[Position[i]]]='T';}}else{Position[i]=-1;Der[i]='F';}}for(i=1; i<=n; i++){if(Der[i]=='T')printf("%d Turning\n",Position[i]);else if(Der[i]=='F')printf("Finished\n");elseprintf("%d %c\n",Position[i],Der[i]);}return 0; }

總結

???????將一個過程的影響因素參數化，再通過代碼運算模擬這個過程，可以實現對部分問題的暴力破解，這實際上也是將真實世界的問題數據化、程序化的過程，對鍛煉理性思維有著一定的積極作用。

---

例題原作者：Inx From BUAA

總結

以上是生活随笔為你收集整理的若干小球碰撞的一种暴力解题法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。