Перекладывание колец по заданному правилу

@комі · Регистрация: 20.10.2022

Студворк — интернет-сервис помощи студентам

Очень нужна помощь задачей. Понятия не имею , что с ней делать и как это делать.

Есть n стержней, на которые нанизывают колечки, с написанными на них последовательными целыми числами. Разрешается класть одно кольцо на другое только тогда,
когда сумма чисел на двух кольцах является квадратом какого-то числа. Узнать
как долго и в какой последовательности это можно делать.

@gunslinger · 05.11.2022, 01:59

Несколько вопросов.
1) Колечек сколько? Бесконечно? Определенное количество?
2) Числа на колечках начинаются с 1 или как?
3)

Сообщение от комі

сумма чисел на двух кольцах является квадратом какого-то числа

Имеются в виду любые два соседних (идущих подряд) кольца на стержне?

@комі · 05.11.2022, 02:09 **[ТС]**

1.Ну, в задаче не уточняется, поэтому можем ограничится каким-то числом. Пусть будет 100.
2. Да, : 1, 2 , 3...( ну и в нашем случае до 100)
3. я понял так: мы кладем колечко на стержень, на это кольцо кладем такое, чтобы сумма была квадратом. а вот третье кольцо уже только в сумме со вторым должно давать квадрат. так понял)

@gunslinger · 05.11.2022, 22:03

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
  // кол-во стержней и колец
  const n = 10, ring_count = 100;
 
  // сначала кольца не лежат на стержне
  // prev_ring_num - переменная для хранения номера "предыдущего" кольца
  unsigned ring[ring_count] = {0}, prev_ring_num;
 
  for (unsigned i = 1; i <= n; i++)  // проходим по стержням
  {
    unsigned j;
    for (j = 1; j <= ring_count; j++)  // "перебираем" все кольца
      if (ring[j - 1] == 0)  // если кольцо еще не на стержне
      {
        prev_ring_num = j;  // запоминаем номер первого "свободного" кольца (не находящегося на стержне)
        ring[j - 1] = i;  // запоминаем номер стержня, на которое положили кольцо
        break;  // выходим из цикла
      }
 
    // проверяем кольца, начиная с первого "свободного" (не находящегося на стержне) кольца
    for (j = prev_ring_num + 1; j <= ring_count; j++)
      if (ring[j - 1] == 0)  // если кольцо еще не на стержне
      {
        double tmp = sqrt(j + prev_ring_num);  // находим корень из суммы значений на кольцах
        if (tmp == int(tmp))  // если корень - целое число
        {
          prev_ring_num = j;  // запоминаем номер нового кольца
          ring[j - 1] = i;  // запоминаем номер стержня, на которое положили кольцо
        }
      }
  }
 
  // вывод результатов; всего стержней - n, колец - ring_count
 
  // счетчик колец на стержнях и общее кол-во колец на стержнях
  unsigned count[n] = {0}, total = 0;
  for (unsigned i = 1; i <= n; i++)  // проходим по стержням
  {
    // выводим номер стержня i
 
    for (unsigned j = 1; j <= ring_count; j++)  // "перебираем" кольца
      if (ring[j - 1] == i)  // если кольцо на i-ом стержне
      {
        // выводим номер кольца (значение на нем) j
 
        // считаем (и выводим, если нужно), сколько колец на стержне
        count[i - 1]++;
      }
 
    // считаем общее кол-во колец на стержнях
    total += count[i - 1];
  }
 
  // выводим общее кол-во колец total на n стержнях

Некоторые результаты:

Перекладывание колец по заданному правилу

@комі · 06.11.2022, 00:41 **[ТС]**

Большое спасибо!!! Просто спасли меня. А то на физфаке не хватает времени, чтобы предоставить программированию должное внимание. И так небольшие проблемки с основным материалом)

Добавлено через 22 минуты
ой, а у меня проблемка. Я ввел нужные математические библиотеки и она запускает, но в консоли просто пусто
#include <iostream>

#include <cstdio>
#include <math.h>

using namespace std;
int main()
{
// кол-во стержней и колец
const int n = 10, ring_count = 100;

// сначала кольца не лежат на стержне
// prev_ring_num - переменная для хранения номера "предыдущего" кольца
unsigned ring[ring_count] = {0}, prev_ring_num;

for (unsigned i = 1; i <= n; i++) // проходим по стержням
{
unsigned j;
for (j = 1; j <= ring_count; j++) // "перебираем" все кольца
if (ring[j - 1] == 0) // если кольцо еще не на стержне
{
prev_ring_num = j; // запоминаем номер первого "свободного" кольца (не находящегося на стержне)
ring[j - 1] = i; // запоминаем номер стержня, на которое положили кольцо
break; // выходим из цикла
}

// проверяем кольца, начиная с первого "свободного" (не находящегося на стержне) кольца
for (j = prev_ring_num + 1; j <= ring_count; j++)
if (ring[j - 1] == 0) // если кольцо еще не на стержне
{
double tmp = sqrt(j + prev_ring_num); // находим корень из суммы значений на кольцах
if (tmp == int(tmp)) // если корень - целое число
{
prev_ring_num = j; // запоминаем номер нового кольца
ring[j - 1] = i; // запоминаем номер стержня, на которое положили кольцо
}
}
}

// вывод результатов; всего стержней - n, колец - ring_count

// счетчик колец на стержнях и общее кол-во колец на стержнях
unsigned count[n] = {0}, total = 0;
for (unsigned i = 1; i <= n; i++) // проходим по стержням
{
// выводим номер стержня i

for (unsigned j = 1; j <= ring_count; j++) // "перебираем" кольца
if (ring[j - 1] == i) // если кольцо на i-ом стержне
{
// выводим номер кольца (значение на нем) j

// считаем (и выводим, если нужно), сколько колец на стержне
count[i - 1]++;
}

// считаем общее кол-во колец на стержнях
total += count[i - 1];
}

// выводим общее кол-во колец total на n стержнях
}

Добавлено через 31 секунду

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
 
#include <cstdio>
#include <math.h>
 
using namespace std;
int main()
{
// кол-во стержней и колец
  int n = 5,  ring_count = 56;
 
  // сначала кольца не лежат на стержне
  // prev_ring_num - переменная для хранения номера "предыдущего" кольца
  unsigned ring[ring_count] = {0}, prev_ring_num;
 
  for (unsigned i = 1; i <= n; i++)  // проходим по стержням
  {
    unsigned j;
    for (j = 1; j <= ring_count; j++)  // "перебираем" все кольца
      if (ring[j - 1] == 0)  // если кольцо еще не на стержне
      {
        prev_ring_num = j;  // запоминаем номер первого "свободного" кольца (не находящегося на стержне)
        ring[j - 1] = i;  // запоминаем номер стержня, на которое положили кольцо
        break;  // выходим из цикла
      }
 
    // проверяем кольца, начиная с первого "свободного" (не находящегося на стержне) кольца
    for (j = prev_ring_num + 1; j <= ring_count; j++)
      if (ring[j - 1] == 0)  // если кольцо еще не на стержне
      {
        double tmp = sqrt(j + prev_ring_num);  // находим корень из суммы значений на кольцах
        if (tmp == int(tmp))  // если корень - целое число
        {
          prev_ring_num = j;  // запоминаем номер нового кольца
          ring[j - 1] = i;  // запоминаем номер стержня, на которое положили кольцо
        }
      }
  }
 
  // вывод результатов; всего стержней - n, колец - ring_count
 
  // счетчик колец на стержнях и общее кол-во колец на стержнях
  unsigned count[n] = {0}, total = 0;
  for (unsigned i = 1; i <= n; i++)  // проходим по стержням
  {
    // выводим номер стержня i
 
    for (unsigned j = 1; j <= ring_count; j++)  // "перебираем" кольца
      if (ring[j - 1] == i)  // если кольцо на i-ом стержне
      {
        // выводим номер кольца (значение на нем) j
 
        // считаем (и выводим, если нужно), сколько колец на стержне
        count[i - 1]++;
      }
 
    // считаем общее кол-во колец на стержнях
    total += count[i - 1];
  }
 
  // выводим общее кол-во колец total на n стержнях
  }

Добавлено через 23 минуты
все , разобрался , я же про выводы забыл)))

@gunslinger · 06.11.2022, 04:59

Если нужно, "оригинальный вывод в билдере через Memo":

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
  // вывод результатов; всего стержней - n, колец - ring_count
  Memo->Text = "";
  Memo->Lines->Add("");
  Memo->Lines->Add("     Всего: стержней - " + String(n) + ", колец - " + String(ring_count));
  Memo->Lines->Add("");
 
  // счетчик колец на стержнях и общее кол-во колец на стержнях
  unsigned count[n] = {0}, total = 0;
  for (unsigned i = 1; i <= n; i++)  // проходим по стержням
  {
    // выводим номер стержня i
    Memo->Lines->Add("     стержень № " + String(i));
    String res = "";
 
    for (unsigned j = 1; j <= ring_count; j++)  // "перебираем" кольца
      if (ring[j - 1] == i)  // если кольцо на i-ом стержне
      {
        // запоминаем номер кольца (значение на нем) j
        res += " " + String(j);
 
        // считаем, сколько колец на стержне
        count[i - 1]++;
      }
 
    // считаем общее кол-во колец на стержнях
    total += count[i - 1];
 
    // выводим кол-во колец на стержне count[i - 1] и их номера (значения) res
    Memo->Lines->Add("     кольца (" + String(count[i - 1]) + " шт.):"
                     + (res == "" ? String(" отсутствуют") : res));
    Memo->Lines->Add("");
  }
 
  // выводим общее кол-во колец total на n стержнях
  Memo->Lines->Add("     Всего колец на " + String(n) + " стержнях: " + String(total));

В том коде, что я предоставил ранее, пытаясь упростить вывод, есть некоторые косяки:
count[i - 1] нужно выводить примерно там, где считается total (строка №50 кода).
Короче, посмотри исходный код в этом посте и сделай вывод по той же логике (в том же порядке по крайней мере).
Я с "консолью" не очень дружу, так как ей не пользуюсь от слова совсем.

Добавлено через 14 минут
Возможно, "код алгоритма" (до вывода) можно (теоретически?) упростить (там есть достаточно "повторяющегося" кода), но я не стал сильно мудрить. Перфекционизм, конечно, дело хорошее, но в разумных пределах.

Добавлено через 1 час 4 минуты
Хотя... Немного причесал "код алгоритма":

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
  const n = 10, ring_count = 100;  // кол-во стержней и колец
  unsigned ring[ring_count] = {0};  // сначала кольца не лежат на стержне
 
  for (unsigned i = 1; i <= n; i++)  // проходим по стержням
  {
    unsigned prev_ring_num = 0;  // переменная для хранения номера "предыдущего" кольца
 
    // условие "пропуска" (учитываем или нет) первого кольца на стержне [ПКнаС] (1 - да, 0 - нет)
    bool skip_1st_ring_on_rod = 0;
 
    for (unsigned j = prev_ring_num + 1; j <= ring_count; j++)  // "перебираем" кольца
      if (ring[j - 1] == 0)  // если кольцо еще не на стержне
      {
        if (skip_1st_ring_on_rod)  // если "пропускаем" ПКнаС
        {
          double tmp = sqrt(j + prev_ring_num);  // находим корень из суммы значений на кольцах
          if (tmp == int(tmp))  // если корень - целое число
          {
            prev_ring_num = j;  // запоминаем номер нового (первого на стержне) кольца
            ring[j - 1] = i;  // запоминаем номер стержня, на которое положили кольцо
          }
        }
        else  // иначе (если !skip_1st_ring_on_rod - не "пропускаем" ПКнаС)
        {
          // запоминаем номер первого "свободного" кольца (не находящегося еще на стержне)
          prev_ring_num = j;
 
          ring[j - 1] = i;  // "кладем" кольцо на стержень; запоминаем, что сделали
          skip_1st_ring_on_rod = 1;  // далее будем "пропускать" ПКнаС
        }
      }
  }

Добавлено через 2 часа 9 минут
В строке

C++
19
            prev_ring_num = j;  // запоминаем номер нового (первого на стержне) кольца

комментарий должен быть

// запоминаем номер нового кольца

(фраза "первого на стержне" ошибочна).

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@комі 0 / 0 / 0 Регистрация: 20.10.2022 Сообщений: 16

	Перекладывание колец по заданному правилу 05.11.2022, 01:49. Показов 894. Ответов 5 Метки hard, help me, mathematic, олимпиада, олимпиадная задача, олимпиадное программирование, с++, с++ 1 курс, с++ 1курс while, с++ 2 курс, с++ algebra (Все метки) Очень нужна помощь задачей. Понятия не имею , что с ней делать и как это делать. Есть n стержней, на которые нанизывают колечки, с написанными на них последовательными целыми числами. Разрешается класть одно кольцо на другое только тогда, когда сумма чисел на двух кольцах является квадратом какого-то числа. Узнать как долго и в какой последовательности это можно делать. 0

@комі 0 / 0 / 0 Регистрация: 20.10.2022 Сообщений: 16
	05.11.2022, 02:09 [ТС]
	1.Ну, в задаче не уточняется, поэтому можем ограничится каким-то числом. Пусть будет 100. 2. Да, : 1, 2 , 3...( ну и в нашем случае до 100) 3. я понял так: мы кладем колечко на стержень, на это кольцо кладем такое, чтобы сумма была квадратом. а вот третье кольцо уже только в сумме со вторым должно давать квадрат. так понял) 0

Перекладывание колец по заданному правилу

Решение