C++ долго долго Int

Question

Так что у меня следующая проблема:

Там будет большая конференция в следующем месяце в городе. Друзья обычно имеют тенденцию прибывать и регистрироваться вместе, поэтому они также в конечном итоге сидят рядом друг другу и общаются с людьми, которых они уже знают. В для того, чтобы немного подправить вещи, организаторы конференции придумали систему, чтобы «перетасовать» порядок обслуживающего персонала и, таким образом, получить их для знакомства с новыми людьми.

Система работает следующим образом: первый человек, прибывший на конференцию регистрации , получает билет с номером a1, случайно выбранным Организаторами. Каждый из следующих лиц получает новый билет с номером ai = (ai - 1 × 31334) mod 31337 и находит свою соответствующую позицию в очереди, только за последним лицом, которое имеет число меньшее или равное чем аи. Это означает, что номера билетов в очереди всегда должны быть в порядке, и если в этой группе уже много человек с таким же номером, последнее прибытие должно быть последним в этой группе.

Ваша задача - написать компьютерную программу, которая поможет обслуживающим персонажам найти их правильное положение в очереди.

Пример. С учетом первоначального номера авиабилета a1 = 7546 найдите позицию в очереди 6-го лица. Итак, вход здесь [7546, 6].

Обсуждение: первое прибывающее лицо получает билет a1 = 7546 и стоит в передней части очереди. Второй человек получает билет a2 = (7546 × 31334) mod 31337 = 8699 и поэтому занимает второе место в очереди. Затем третий человек получает билет с номером a3 = (8699 × 31334) по модулю 31337 = 5240 и, следовательно, получает , чтобы перепрыгнуть в очередь и встать в позицию 1, перемещая других людей в очередь в одну позицию до назад. То есть, очередь теперь выглядит так:

1: 5240 (3), 2: 7546 (1), 3: 8699 (2) где номера билетов находятся в возрастающий заказ, а число в родительском доме является оригиналом заказать в , который участники пришли на конференцию.

Продолжая эту последовательность, четвертый, пятый и шестой участники получат номера билетов a4 = 15617, a5 = 15823 и a6 = 15205; так что будет выглядеть так:

1: 5240 (3), 2: 7546 (1), 3: 8699 (2), 4: 15205 (6), 5: 15617 (4), 6 : 15823 (5), то есть шестой человек, прибывающий, встает на позицию 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; 
} 

Он отображает правильные вещи для небольших чисел, но когда я ввожу более крупные из них здесь возникает проблема, потому что она просто ломается. Например, он отображает 4 для [7253,10] и 1 для [24284,10], но он прерывается при вводе [12879,505]. Любая идея?

Answer 1

Даже не выходя за свой код, я могу сказать, что число переполняет не должно быть проблемой даже для signed int с:

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 операторы с блоками { }, даже если у вас есть только одно выражение, или если вы добавите код в будущем, вы забудете их и получите «забавное» время отладки.

В качестве общей рекомендации - сохранить себя некоторые горе и сделать привычку использовать случай Yoda: 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; 
}