Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Игры разума
Перезагрузить страницу Последовательность с пропущенными числами
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 02.08.2007, 13:42

Вот рассказали такую задачу.

Есть массив целых чисел от 0 до N, числа не упорядочены. Одного числа не хватает, надо найти - какого именно как можно быстрее и не используя дополнительной памяти (но объявить дополнительно несколько целочисленных переменных, как я понял, можно - нельзя только создавать второй массив).
Следующий вариант - всё то же самое, но не хватает двух чисел.
Ответить с цитированием
  (#2 (permalink)) Старый
Garik Garik вне форума
Member
 
Сообщений: 6,201
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 07.06.2002
По умолчанию 02.08.2007, 14:31

Для одного числа задача примитивная (если я понял её правильно).
Сумма всех чисел вычисляется как сумма арифметической прогрессии: S = N * (N + 1) / 2. Далее вычитаем по очереди все числа и в остатке получаем недостающее.
Ответить с цитированием
  (#3 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 02.08.2007, 17:18

Правильно понял, примитивная. А что для двух?
Ответить с цитированием
  (#4 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 02.08.2007, 18:21

(1).S = N/2 * (N/2 + 1) / 2 и суммировать только числа меньшие N/2
(2). проверить отсутствие числа среди этих чисел
(3). таким же примерно макаром проверить отсутствие числа среди N/2...N
(4).если числа в разных диапазонах - то найти методом Гарика.
(5). если нет, то делить диапазоны пока не (4)

Первое что в голову пришло


импортирован с progz.ru
Ответить с цитированием
  (#5 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 03.08.2007, 16:58

(1) вычесть из N * (N + 1) / 2 сумму всех чисел (получим А)
(2) разделить N! на произведение всех чисел (получим В)
(3) ответ (-A + sqrt(A**2 - 4B))/2 и (-A - sqrt(A**2 - 4B))/2


импортирован с progz.ru
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 03.08.2007, 18:57

Во-первых, в большинстве случаев мы получаем деление на 0 при вычислении B. Во-вторых:

Код:
from math import *
from random import *

def factorial(N):
    if N == 0: return 1
    
    return N*factorial(N-1)

def get_missing(seq, N):
    A = N*(N+1)/2 - sum(seq)
    B = factorial(N)/reduce(lambda x, y: x*y, seq)
    return ( (-A + sqrt(A*A - 4*B))/2, (-A - sqrt(A*A - 4*B))/2 )

seq = range(10)
seq.remove(0)
seq.remove(5)
shuffle(seq)
print seq
[1, 9, 4, 6, 7, 2, 3, 8]

Какое N надо взять - 9 или 10? Так или иначе:
Код:
print get_missing(seq, 9)
(-1.3819660112501051, -3.6180339887498949)
Код:
print get_missing(seq, 10)
(-5.0, -10.0)

Либо я что-то напутал, либо у тебя что-то не сходится.
Ответить с цитированием
  (#7 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 03.08.2007, 20:36

ну во-первых, я опечатался: в (-A + sqrt(A**2 - 4B))/2 и (-A - sqrt(A**2 - 4B))/2 минус перед А не нужен.
Во-вторых я невнимательно прочитал условие, и не заметил, что последовательность начинается с 0, а не с 1

В случае последовательности, начинающейся с нуля проще сделать иначе:
Код:
from math import *
from random import *


def get_missing(seq):
    N = len(seq)+2
    A = (N-1)*N/2 - sum(seq)
    B = sum(map(lambda x: x*x,range(N))) - sum(map(lambda x: x*x,seq))
    return ( (A + sqrt(2*B - A*A))/2, (A - sqrt(2*B - A*A))/2 )


seq = range(10)
seq.remove(0)
seq.remove(5)
shuffle(seq)
print seq
print get_missing(seq)
Следует заметить, что для суммы квадратов арифм. последовательности ( sum(map(lambda x: x*x,range(N))) ) существует готовая формула типа (N-1)*N/2, но я её не помню.

Кстати, использование функции map() в данной конкретной задаче не совсем корректно..


импортирован с progz.ru
Ответить с цитированием
  (#8 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 04.08.2007, 10:05

Вроде, работает. map(), я думаю, не страшен, потому что мы ж знаем, что сумма квадратов легко считается и без него, уж пусть, для краткости

Человек, который мне рассказал эту задачу, получил ее на телефонном интервью в Google. Он придумал другой, довольно забавный алгоритм ее решения - у меня на рабочем компе осталась питоновская программа, может, в понедельник запощу сюда. Суть там сводится к расстановке чисел так, чтобы значение числа совпадало с его индексом в массиве, а на месте отсутствующих чисел появляются, допустим, "-1".

А я сам тоже придумал решение через сумму квадратов, но не дорешал
Ответить с цитированием
  (#9 (permalink)) Старый
Narwal Narwal вне форума
Member
 
Сообщений: 1,039
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 07.10.2003
По умолчанию 05.08.2007, 02:15

Цитата:
Он придумал другой, довольно забавный алгоритм ее решения... Суть там сводится к расстановке чисел так, чтобы значение числа совпадало с его индексом в массиве, а на месте отсутствующих чисел появляются, допустим, "-1".
Если я правильно понял, то это т. н. - "цифровая сортировка"
( Есть, кстати, прикольная книжка, называется "Жемчужины программирования". В ней, например, есть задача - имеется файл, содержащий n чисел, каждое из которых не превосходит N = 10^7. Требуется отсортировать этот файл при ограничениях - расход памяти не должен быть больше 1 мб и время работы не должно превосходить несколько минут. Если время работы будет составлять 10 секунд дальнейшая оптимизация не потребуется )
Ответить с цитированием
  (#10 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 12.10.2007, 19:34

Собственно, вот эта программа:
Код:
import random

def find_missing(seq):
    
    sorted = -1
    cash = -1
    pos = 0
    while True:
        if sorted >= len(seq)-1: break
        print seq
        cash, seq[pos] = seq[pos], cash
        if cash == -1:
            sorted += 1
            pos = sorted + 1
            continue
        pos = cash        


N = 10
seq = range(N)
random.seed()
miss1 = random.randint(0, N-1)
miss2 = random.randint(0, N-1)
seq.remove(miss1)
seq.remove(miss2)
random.shuffle(seq)
w_seq = seq + [-1 for x in range(len(seq), N)]
print miss1, miss2
print w_seq
print "----------"
find_missing(w_seq)
print "----------"
print w_seq
for i, val in enumerate(w_seq):
    if val == -1:
        print "Missing: " + `i`
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Как сделать последовательность sasha-77793 C++ на Unix 0 25.05.2011 21:09
Последовательность непонятная Dixx Prolog 0 14.05.2010 00:43
Посчитать последовательность a= n! / n^n stella111199 Lisp 2 12.04.2010 16:22
Действия с комплексными числами nilov Prolog 8 02.03.2010 17:12
Задача на последовательность Debro Prolog 5 29.12.2009 22:22
Последовательность HellFire Pascal 17 28.12.2007 21:50
Последовательность 4 8 15 16 23 42 Alexiski Офтопик 1 05.10.2007 15:40
Как работать с большими числами при ASM/C bugZex Assembler 29 09.01.2007 18:30
Как передавать последовательность Kudray Железо. Написание драйверов 7 05.03.2006 16:27
Вычисления с большими числами Redrik_Shuxxaart Задания за деньги 4 11.01.2006 11:16
Операции над двоичными числами Винитарх Prolog 5 05.07.2005 11:12



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов