Странно работает цикл for в C#

196

11 сентября 2018, 11:30

Делал задачку на цикл, решил пошагово посмотреть как все работает и встал в ступор. Почему не выходит из цикла когда j = 4?

int[] arr = { 1, 3, 2, 6, 1 };
for (int i = 0, j = 1; j <= arr.Length - 1; j++)
{
    int number = arr[i];
    if (i == arr.Length - 1)
        break;
    if (number + arr[j] == k || (number + arr[j]) % k == 0)
        result++;
    if (j == arr.Length - 1)
    {
        i++;
        j = i;
    }
}

Answer 1

Вначале замечание:

Условие

if (number + arr[j] == k || (number + arr[j]) % k == 0)

избыточно. Достаточно проверки

if ((number + arr[j]) % k == 0)

Как я понял, смысл программы подсчитать количество пар чисел массива, сумма которых делится на k. Почему бы не упростить задачу и повысить читабельность кода при помощи второго вложенного цикла?

int[] arr = { 1, 3, 2, 6, 1 };
for (int i = 0; i < arr.Length - 1; i++) {
  for (int j = i + 1; j < arr.Length; j++) {
    if ((arr[i] + arr[j]) % k == 0)
      result++;
  }
}

Answer 2

Вставлю свои пять копеек, как бывший участник егэ по информатике:

Вложенные циклы с условием, зависимым от N, делают время выполнения программы зависимым от N*N. Более правильным было бы:

Разложить k на слагаемые (например, при k = 5 это 0 + 5, 1 + 4, 2 + 3).
Один раз пройтись по входному массиву и посчитать, сколько из чисел при делении на k какой остаток дают и записать сведения в другой массив, где индексом был бы остаток от деления, а значением - количество чисел во входном массиве, дающих такой остаток.
Циклом, проходящим по этому новому массиву, посчитать, сколько комбинаций удовлетворяют условиям(например, если чисел, дающих при делении на 5 остаток 1 у нас 10, а остаток 4 - 3, то из них мы можем составить 10 * 3 = 30 пар, но нужно еще учесть числа, дающие остаток 0 - для них работает формула n = m(m - 1)/2, где m - количество чисел, дающих при делении на k остаток 0, а n - количество пар, образуемых такими числами).

Но при не очень большой длине входящих массивов целесообразней, конечно же, использовать вложенный цикл.