C++長長的詮釋

Question

所以，我有以下問題：

會有下個月在全市大型會議。通常朋友 傾向於到達並一起註冊，所以他們最後也會坐在對方 和他們已經知道的人聊天。在 爲了讓事情有點發揮，會議組織者想出了一個系統來「洗牌」服務員的順序，並因此，讓他們 結識新朋友。

該系統的工作原理如下：第一個到達 會議註冊的人獲得一張票號爲a1，組織者隨機選擇 。以下每個人到達後會得到一張新號碼，其號碼爲ai =（ai - 1×31334）mod 31337，並且在隊列中找到其相應的位置 ，在最後一個人的後面 的號碼小於或等於AI。這意味着隊列中的票號 應該始終按順序排列，並且如果已有很多具有相同號碼的人，則最近到達的應該是該組中的最後一個 。

你的任務是編寫一個計算機程序，它將幫助服務員 找到他們在隊列中的正確位置。

示例給定初始票證號碼a1 = 7546，在第6個人到達的隊列中找到位置 。所以這裏的輸入是[7546， 6]。

討論：第一個到達的人獲得票a1 = 7546和 站在隊列的前面。第二個人獲得門票a2 =（7546×31334）mod 31337 = 8699，因此站在隊列中的第二個位置。第三個人到達然後獲得票號 ，其中號碼a3 =（8699×31334）mod 31337 = 5240，因此，得到 跳過隊列並站在位置1，將其他人 移動到隊列一位置到背部。也就是說，隊列如下所示：

1：5240（3），2：7546（1），3：8699（2）其中票號爲 遞增順序，parentesis中的數字爲原始參與者到達會議的 。

繼續這個順序，第四，第五和第六個參與者 將得到票號a4 = 15617，a5 = 15823和a6 = 15205;因此 隊列將如下所示：

1：5240（3），2：7546（1），3：8699（2），4：15205（6），5：15617（4），6 ： 15823（5）即第6個到達的人站在隊列中的 位置4。

答：4

而下面的C++代碼：

#include <iostream> 
using namespace std; 
int main() 
{ 
    int n, i, poz, ok; 
    long long int a, v[100], aux; 
    cout << "v[1]= "; cin >> v[1]; 
    cout << "n= "; cin >> n; 
    for (i=2; i<=n; i++) 
     v[i]=(v[i-1]*31334)%31337; 
    a=v[n]; 
    do 
    { 
     ok=0; 
     for (i=1; i<n; i++) 
      if (v[i]>v[i+1]) 
      { 
       aux=v[i]; 
       v[i]=v[i+1]; 
       v[i+1]=aux; 
       ok=1; 
      } 
    }while (ok==1); 
    for (i=1; i<=n; i++) 
     if (v[i]==a) 
      poz=i; 
    cout << poz; 
    return 0; 
} 

它顯示了正確的事情，對於小的數字，但是當我進入較大的下面就是我的問題，因爲它只是打破。 例如，[7253,10]顯示4，[24284,10]顯示1，但輸入[12879,505]時顯示中斷。 有什麼想法？

Answer 1

即使不打算在你的代碼，我可以說，整數溢出不應該是一個問題，即使是signed int S：

31337² = 982,007,569這是111010100010000011111100010001，一個30位的數字。

因此，在這裏不應該超過MAX INT，即(2^31)-1 = 2,147,483,647。 就像一塊瑣事一樣，long long int將支持高達(2^63)-1 = 9,223,372,036,854,775,807的數字。

需要現在要做的事情就是調試代碼...

按你的錯誤 - 我認爲這個問題是您定義的arrav v 100的尺寸，並試圖找到第505元 - 這本質上是非法的內存訪問，因此是不可預測的。 你對你自己的代碼:)從所有

除了做一個緩衝區溢出，我建議你花一些時間整理你的代碼 - #define或爲您的常量添加const值（數組大小，31337，31334等等） 請記住，C++中的數組以v[0]開頭，而不是v[1] - 無論文字如何描述。這是個錯誤。 封裝for和if語句，即使您只有一個表達式跟隨它們，或者在未來添加代碼時，您會忘記它們，並有一個「有趣」的時間來調試它。

通常建議 - 保存自己的一些悲痛，並使用尤達盒的習慣：1 == ok代替ok == 1因爲筆誤把它變成ok = 1會導致你一個非常討厭的錯誤。

Answer 2

你應該考慮使用一個向量並推回值。

但是你要走出你的陣列。您創建了一個大小爲100的數組，並且您正嘗試在上次測試中使用505個空間。

因此，要麼使用矢量和push_back你的值或增加你的數組的大小。爲了便於使用，我會推薦該載體。

下面是我扔在一起解決您的問題，使用容器和STL函數爲您完成大部分工作。希望這可以幫助你。 =）

#include <iostream> 
#include <vector> 
#include <algorithm> 

using namespace std; 

using LONG64 = long long; 

const int MULTIPLIER = 31334; 
const int MOD = 31337; 

int main() 
{ 
    vector<LONG64> ticket; 

    cout << "v[1]= "; 
    LONG64 seed; 
    cin >> seed; 
    ticket.emplace_back(seed); 

    cout << "n= "; 
    int queue_spot; 
    cin >> queue_spot; 

    for (auto i = 1; i <= queue_spot; ++i) { 
     auto seed_number = (ticket[i - 1] * MULTIPLIER) % MOD; 
     //cout << "\nseed_number " << seed_number; 
     ticket.emplace_back(seed_number); 
    } 

    LONG64 person_ticket_number = ticket[queue_spot - 1]; 

    cout << "\nPerson's ticket number " << person_ticket_number; 

    sort(ticket.begin(), ticket.end()); 

    auto spot = find(ticket.begin(), ticket.end(), person_ticket_number); 

    cout << "\nPerson is in spot " << (spot - ticket.begin()) + 1 << endl; 

    system("PAUSE"); 
    return 0; 
}