Далее представлен калькулятор, при помощи которого можно искать пропущенные номера в последовательности целых чисел. Пример такой последовательности (каждое число на новой строке):
1
2
3
4
6
7
12
13
18
Как видно в последовательности есть пропуски и единичных номеров и нескольких подряд следующих номеров. Например, номер 5 пропущен, а также пропущено два куска: между 8 и 11 и между 14 и 17.
В таком простом примере Вы и сами можете найти пропуски, но если речь идет о тысячах номеров, то калькулятор вам сильно пригодится. Просто скопируйте вашу последовательность в текстовое поле и калькулятор найдет все пропуски между числом в первой и последней строках.
Поиск пропущенных номеров
Использовать регулярные выражения для выделения чисел
Использовать пустые строки как разделители групп
Настройки калькулятора пропусков
Для более сложных случаев имеется несколько настроек:
- Установите флажек «В сжатом виде» чтобы калькулятор выдавал диапазоны последовательных пропусков номеров, например 8 — 11, где 8 начало, а 11 конец последовательного пропуска. В противном случае будет выдана вся последовательность пропущенных номеров, например 8, 9, 10, 11.
- Можно установить галочку «Использовать регулярные выражения для выделения номеров», для выделения чисел из строки при помощи регулярного выражения.
Последняя опция становится актуальной, если в вашем перечне номеров содержатся не только числа, например вот такая последовательность:
1 Бумага побеждает камень
2 Ножницы режут бумагу
3 Камень разрушает ножницы
Вот для таких случаев регулярное выражение выделит числовые данные из этого текста. Регулярное выражение по умолчанию выделяет числа из начала строки, если требуется отредактируйте выражение под вашу задачу.
Учитывая массив n-1 различные целые числа в диапазоне от 1 до n, найти в нем пропущенное число за линейное время.
Например, рассмотрим массив {1, 2, 3, 4, 5, 7, 8, 9, 10} элементы которого различны и находятся в диапазоне от 1 до 10. Недостающее число — 6.
Потренируйтесь в этой проблеме
1. Использование формулы для суммы первых n Натуральные числа
Мы знаем, что сумма первых n натуральные числа можно вычислить по формуле 1 + 2 + … + n = n×(n+1)/2. Мы можем использовать эту формулу, чтобы найти пропущенное число.
Идея состоит в том, чтобы найти сумму целых чисел от 1 до n+1 используя приведенную выше формулу, где n размер массива. Также вычислите фактическую сумму целых чисел в массиве. Теперь недостающее число будет разницей между ними.
Этот подход демонстрируется ниже на C, Java и Python:
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 |
#include <stdio.h> // Находим пропущенное число в заданном массиве int getMissingNumber(int arr[], int n) { // фактический размер `n+1`, так как в массиве отсутствует число int m = n + 1; // получить сумму целых чисел от 1 до `n+1` int total = m*(m + 1)/2; // получаем реальную сумму целых чисел в массиве int sum = 0; for (int i = 0; i < n; i++) { sum += arr[i]; } // недостающее число — это разница между ожидаемой суммой // и фактическая сумма return total — sum; } int main() { int arr[] = { 1, 2, 3, 4, 5, 7, 8, 9, 10 }; int n = sizeof(arr)/sizeof(arr[0]); printf(«The missing number is %d», getMissingNumber(arr, n)); return 0; } |
Скачать Выполнить код
результат:
The missing number is 6
Java
|
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 |
import java.util.Arrays; class Main { // Находим пропущенное число в заданном массиве public static int getMissingNumber(int[] arr) { // получаем длину массива int n = arr.length; // фактический размер `n+1`, так как в массиве отсутствует число int m = n + 1; // получить сумму целых чисел от 1 до `n+1` int total = m * (m + 1) / 2; // получаем реальную сумму целых чисел в массиве int sum = Arrays.stream(arr).sum(); // недостающее число — это разница между ожидаемой суммой // и фактическая сумма return total — sum; } public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5, 7, 8, 9, 10 }; System.out.println(«The missing number is « + getMissingNumber(arr)); } } |
Скачать Выполнить код
результат:
The missing number is 6
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
# Найти недостающее число в заданном списке def getMissingNumber(arr): # получить длину массива n = len(arr) # Фактический размер # равен `n+1`, так как в списке отсутствует номер. m = n + 1 # получить сумму целых чисел от 1 до `n+1` total = m * (m + 1) // 2 # пропущенное число – это разница между ожидаемой суммой и # фактическая сумма целых чисел в списке return total — sum(arr) if __name__ == ‘__main__’: arr = [1, 2, 3, 4, 5, 7, 8, 9, 10] print(‘The missing number is’, getMissingNumber(arr)) |
Скачать Выполнить код
результат:
The missing number is 6
2. Использование оператора XOR
Мы знаем, что XOR двух одинаковых чисел отменяет друг друга. Мы можем воспользоваться этим фактом, чтобы найти недостающее число в массиве с ограниченным диапазоном.
Идея состоит в том, чтобы вычислить XOR всех элементов массива и вычислить XOR всех элементов от 1 до n+1, куда n размер массива. Теперь недостающее число будет XOR между ними.
Этот подход демонстрируется ниже на C, Java и Python:
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 |
#include <stdio.h> // Находим пропущенное число в заданном массиве int getMissingNumber(int arr[], int n) { // Вычислить XOR всех элементов массива int xor = 0; for (int i = 0; i < n; i++) { xor = xor ^ arr[i]; } // Вычислить XOR всех элементов от 1 до `n+1` for (int i = 1; i <= n + 1; i++) { xor = xor ^ i; } return xor; } int main() { int arr[] = { 1, 2, 3, 4, 5, 7, 8, 9, 10 }; int n = sizeof(arr) / sizeof(arr[0]); printf(«The missing number is %d», getMissingNumber(arr, n)); return 0; } |
Скачать Выполнить код
результат:
The missing number is 6
Java
|
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 |
class Main { // Находим пропущенное число в заданном массиве public static int getMissingNumber(int[] arr) { // Вычислить XOR всех элементов массива int xor = 0; for (int i: arr) { xor = xor ^ i; } // Вычислить XOR всех элементов от 1 до `n+1` for (int i = 1; i <= arr.length + 1; i++) { xor = xor ^ i; } return xor; } public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5, 7, 8, 9, 10 }; System.out.println(«The missing number is « + getMissingNumber(arr)); } } |
Скачать Выполнить код
результат:
The missing number is 6
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
# Найти недостающее число в заданном списке def getMissingNumber(arr): # Вычислить XOR всех элементов в списке xor = 0 for i in arr: xor = xor ^ i # Вычислить XOR всех элементов от 1 до `n+1` for i in range(1, len(arr) + 2): xor = xor ^ i return xor if __name__ == ‘__main__’: arr = [1, 2, 3, 4, 5, 7, 8, 9, 10] print(‘The missing number is’, getMissingNumber(arr)) |
Скачать Выполнить код
результат:
The missing number is 6
Временная сложность обоих рассмотренных выше методов составляет O(n) и не требует дополнительного места, где n это размер ввода.
Пусть пропущенное число равно х.
1. Найдем среднее арифметическое:
(х+3+4+4+7+15+15+16+24)/9=(x+88)/9
2. Упорядочим имеющиеся числа по возрастанию: 3, 4, 4, 7, 15, 15, 16, 24.
Между числами этого упорядоченного ряда где-то нужно вставить число х,
тогда по определению, медианой ряда будет число, расположенное ровно посередине, т.е. 5-ое по
счету число.
Если х<7, то 5-ым числом, т.е. медианой, будет 7, откуда (x+88)/9=7, х=7*9-88=-25<7, т.е. -25 удовлетворяет условию.
Если 7≤х≤15, то медианой будет само х, но тогда (x+88)/9=х, откуда х=11, тоже подходит.
Если х>15, то медиана ряда равна 15, т.е. (x+88)/9=15, откуда х=9*15-88=47.
Ответ: подходят три числа: -25; 11; 47.
Найти пропущенные числа
Опубликовал — Понедельник, 9 июня, 2014 в рубрике Пропущенное число.
Рассмотрим задания из тестов IQ, в которых нужно найти пропущенные числа в данном числовом ряду.
В отличие от заданий в которых требуется найти пропущенное число, здесь требуется найти не одно, а два числа. При этом числовой ряд может подчиняться как одной, так и двум закономерностям (вообще-то, их может быть и больше).
Определить сразу два закона, по которым составлен ряд чисел, в целом, сложнее. Итак, перед вами — 10 заданий.
Найти пропущенные числа:
1) 4; 9; 7; 12; 10; ?; ?
2) 1; 6; 3; 18; 9; ?; ?
3) 2; 11; 8; 9; 32; 7; ?; ?
4) 64; 16; 27; 9; ?; ?; 1; 1
5) 6; 11; 11; 30; 18; 67; ?; ?
6) 96; 7; 48; 14; ?; ?; 12; 56
7) 5; 7; 14; 16; 32; 34; ?; ?
2; 11; 45; ?; ?; 274
9) ?; 2; 4; 7; 6; 4; ?
10) 1; 2; 2; 4; 8; ?; 33; 37; ?
Показать решение
Если найденное вами решение не совпадает с данным ответом, но подчиняется определенной закономерности — это не ошибка. Помните, что тесты IQ составляют люди, и их рассуждения при составлении задачи могут отличаться от ваших.
В этой связи вспоминается детский анекдот, демонстрирующий умение юного ума предлагать нестандартные решения.
Один маленький мальчик задает другому загадку:
— Большое, красное, висит на потолке. Что это?
— Не знаю.
— Мотоцикл!
— А почему на потолке?
— Моя вещь. Куда захочу, туда и поставлю!
Составляйте свои собственные задания, определяйте связь между числами по своим правилам.
Кроме того, что такая гимнастика для мозга, несомненно, способствует развитию интеллекта, этот тренинг поможет вам понять, что вариантов закономерностей — великое множество. И тогда, имея дело с чужими задачами, вы будете готовы видеть большее количество путей, по которым можно повести решение.
Успехов вам!
Вася Иванов
Мореплаватель — имя существительное, употребляется в мужском роде. К нему может быть несколько синонимов.
1. Моряк. Старый моряк смотрел вдаль, думая о предстоящем опасном путешествии;
2. Аргонавт. На аргонавте были старые потертые штаны, а его рубашка пропиталась запахом моря и соли;
3. Мореход. Опытный мореход знал, что на этом месте погибло уже много кораблей, ведь под водой скрывались острые скалы;
4. Морской волк. Старый морской волк был рад, ведь ему предстояло отчалить в долгое плавание.