3

Всем доброго дня! Суть проблемы в цледующем: есть некое число n и его двоичное предсавление, после некоторого количество цыкличных сдвигов вправо двоичное представление сново повтаряется, и нужно выяснить максималное число которое получается из десятичного представления одного из этих сдвигов.

Вот что я пробовал делать

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>

using namespace std;

const int N = 1005;

string to_binary(int x) {
    string s;
    do {
        s.push_back('0' + (x & 1));
    } while (x >>= 1);

    reverse(s.begin(), s.end());
    return s;
}

int get_count_of_repeats(string s) {
    if (s.size() == 1) {
        return 0;
    }
    else {
        string z = s;
        int count = 1;

        char c = z[z.size() - 1];
        for (int i = z.size() - 1; i >= 1; i--) {
            z[i] = z[i - 1];
        }
        z[0] = c;

        while (s != z) {
            char ch = z[z.size() - 1];
            for (int i = z.size() - 1; i >= 1; i--) {
                z[i] = z[i - 1];
            }
            z[0] = ch;
            count++;
        }
        return count;
    }
}


int main() {

    int n;
    cin >> n;

    string binary = to_binary(n);

    if (get_count_of_repeats(binary) == 0) {
        cout << n << endl;
    }
    else {
        int mx = -1000007;
        int count = get_count_of_repeats(binary);
        for (int i = 0; i < count; i++) {
            string z = binary;
            char c = z[z.size() - 1];
            for (int j = z.size() - 1; j >= 1; j--) {
                z[i] = z[i - 1];
            }
            z[0] = c;

            mx = max(mx, stoi(z, nullptr, 2));
            binary = z;
        }
        cout << mx << endl;
    }


    return 0;
}

но мне выдает следующую ошибку

введите сюда описание изображения

помогите пожалуйста решить проблему

5
  • 1
    В этом окошке следует нажать Retry и отладить 21 авг 2020 в 19:30
  • думаю тут понятно что проблема в том что превосходит максимально допустимую длину строки и это случается в to_binary ведь только там я добавляю что то в строку, но не пойму как это исправить 21 авг 2020 в 19:35
  • 1
    попробовал уронить программу - не получается. какое число вводите?
    – KoVadim
    21 авг 2020 в 19:38
  • я ввожу число 19 но проблему нужно решить для чисел до 32000, и я думаю что это решение не сработает в любом случаи 21 авг 2020 в 19:40
  • и желательно используя битовые операции, как видите я использовал их только в to_binary 21 авг 2020 в 19:47

2 ответа 2

3

В main

 for (int j = z.size() - 1; j >= 1; j--) {
            z[i] = z[i - 1];
        }

должно быть

for (int j = z.size() - 1; j >= 1; j--) {
            z[j] = z[j - 1];
        }

Копипаст и однобуквенные переменные плохую службу сослужили

3

Задача естественным образом решается без всяких преобразований числа в строку символов, применением к самому числу (целой переменной) операций для побитового сдвига (>> и <<) и операции |.

Например, для циклического сдвига вправо надо сдвинуть все биты числа на один разряд вправо и записать в старший разряд значение младшего (до сдвига).

#include <iostream>
#include <limits.h>  // CHAR_BIT definition

using namespace std;  
  

int main () {
  unsigned int n,
    shift_size = sizeof(n) * CHAR_BIT - 1;  // number of bits in the number minus one

  if (cin >> n) {
    unsigned int max_val = n,
      v = n;

    do {
      v = (v >> 1) | (v << shift_size); // rotate to right
      //v = (v << 1) | (v >> shift_size); // rotate to left
      if (v > max_val)
        max_val = v;
    } while (n != v);

    cout << "max = " << max_val  << '\n';
  } else 
    cout << "Nothing to do (not number)\n";
}

Если циклический сдвиг нужно делать только на диапазоне значащих бит исходного числа (например, для числа 5 (101b) это 3 бита), то добавим функцию, вычисляющую этот диапазон

// ugly implementation of FFS, but simple and short
unsigned int get_bitsize (unsigned int n) {
  unsigned int i;
  for (i = 0; n; n >>= 1, i++);

  return i;
}

величину сдвига для вращения вычислим как shift_size = get_bitsize(n) - 1

а сам сдвиг вправо будем делать с маскированием "лишних" (получающихся в результате сдвига) бит -- ((v >> 1) | (v << shift_size)) & mask),

где mask состоит из бит, равных 1 для диапазона.
(степень двойки (т.е. 1 << get_bitsize(n)) минус 1 делает соответствующую маску).

В общем, получаем вот такую часть кода для перебора

  if (cin >> n) {
      
    unsigned int size = get_bitsize(n),
      shift_size = size - 1, 
      mask = size == sizeof(n) * CHAR_BIT ? ~0 : (1 << size) - 1;
    
    unsigned int max_val = n,
      v = n;

    if (size > 1)
      do {
        v = ((v >> 1) | (v << shift_size)) & mask; // rotate to right
        if (v > max_val)
          max_val = v;
      } while (n != v);

    cout << "max = " << max_val << '\n';
  }
3
  • код написанный мной не работал, и этот выдает неправильный ответ 22 авг 2020 в 5:05
  • @E_d_u_a_r_d, можете уточнить в чем ошибка? На каких входных данных какой должен получаться результат? Может быть вы не описали что-то в вопросе, например, что крутить надо не все биты, а только их часть, начиная от старшего значимого в исходном числе?
    – avp
    22 авг 2020 в 8:35
  • @E_d_u_a_r_d Задайте отдельный вопрос про реализацию с использованием битовой арифметики, приведите побольше подробностей задачи
    – MBo
    22 авг 2020 в 16:39

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.