Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование в широком смысле слова > Математика

Математика Методы математического моделлирования, программирование математических концепций, роль математики в создании игр

Ответ
 
Опции темы
Старый 31.08.2009, 21:44   #1
Dream
быдло
 
Регистрация: 05.08.2007
Сообщений: 1,435
Написано 614 полезных сообщений
(для 1,489 пользователей)
Радость Простенькая задачка)

Задачка такая:
Есть последовательность чисел от 1(0) до 1000, одного числа в этой последовательности нету, весь порядок записан в масив,на месте где должно было быть пропущеное число - 0.
Предложите самый быстрый способ поиска этого числа))
мой вариант
	int arrInt[1000];

	for(int i=0;i<1000;i++)
	{
		if(i!=23)
		{
			arrInt[i]=i;
		}
		else
		{
			arrInt[i]=0;
		}
	}
	int need_sum=0;
	int have_sum=0;
	for(int i=0;i<1000;i++)
	{
		need_sum+=i;
		have_sum+=arrInt[i];
	}
	int digits=need_sum-have_sum;
P.S. язык реализации значения не имеет
(Offline)
 
Ответить с цитированием
Старый 31.08.2009, 22:01   #2
IGR
Blitz's Shame !!
 
Регистрация: 31.03.2007
Сообщений: 3,639
Написано 832 полезных сообщений
(для 2,013 пользователей)
Ответ: Простенькая задачка)

for(int i=1;i<1000;i++) {
if(arrInt[i] == 0) {
int res = i;
break;
}
}
как-то так...
(Offline)
 
Ответить с цитированием
Старый 01.09.2009, 05:51   #3
Dream
быдло
 
Регистрация: 05.08.2007
Сообщений: 1,435
Написано 614 полезных сообщений
(для 1,489 пользователей)
Ответ: Простенькая задачка)

а без перебора всего масива?
(Offline)
 
Ответить с цитированием
Старый 01.09.2009, 10:36   #4
NitE
злобный флудер
 
Регистрация: 10.07.2007
Сообщений: 2,585
Написано 789 полезных сообщений
(для 1,476 пользователей)
Ответ: Простенькая задачка)

в посте №2 перебор иднт только до того как находится 0
(Offline)
 
Ответить с цитированием
Старый 01.09.2009, 10:45   #5
jimon
 
Сообщений: n/a
Ответ: Простенькая задачка)

DimasSup
если учитывать ту информацию что ты предоставил - без перебора никак
 
Ответить с цитированием
Старый 01.09.2009, 11:29   #6
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,935 пользователей)
Ответ: Простенькая задачка)

В формулировке нет ошибок? На месте пропуска 0 или разрыв типа: 1 2 4 5 ?
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Старый 01.09.2009, 13:21   #7
IGR
Blitz's Shame !!
 
Регистрация: 31.03.2007
Сообщений: 3,639
Написано 832 полезных сообщений
(для 2,013 пользователей)
Ответ: Простенькая задачка)

for(int i=0;i<1000;i++)
{
need_sum+=i;
have_sum+=arrInt[i];
}
эм... ну у тебя же тоже перебор !!
(Offline)
 
Ответить с цитированием
Старый 01.09.2009, 18:09   #8
Horror
Бывалый
 
Регистрация: 09.09.2006
Сообщений: 656
Написано 54 полезных сообщений
(для 110 пользователей)
Ответ: Простенькая задачка)

а может при запись в масив, запомнить где ноль)
(Offline)
 
Ответить с цитированием
Старый 01.09.2009, 19:24   #9
IGR
Blitz's Shame !!
 
Регистрация: 31.03.2007
Сообщений: 3,639
Написано 832 полезных сообщений
(для 2,013 пользователей)
Ответ: Простенькая задачка)

а может при запись в масив, запомнить где ноль)
жжешь !!

я загадал где ноль !! как ты угадаешь ?? перебор ??
(Offline)
 
Ответить с цитированием
Старый 02.09.2009, 16:27   #10
Dream
быдло
 
Регистрация: 05.08.2007
Сообщений: 1,435
Написано 614 полезных сообщений
(для 1,489 пользователей)
Ответ: Простенькая задачка)

Да, я ошибся, место пропуска не заносится в масив, как написал импер. Способы решения?
(Offline)
 
Ответить с цитированием
Старый 02.09.2009, 16:56   #11
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,935 пользователей)
Ответ: Простенькая задачка)

бинарный поиск на базе критерия
m[i]!=i
m[i]<i
m[i]>i
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Старый 02.09.2009, 17:48   #12
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,935 пользователей)
Ответ: Простенькая задачка)

на скорую руку - ногами не бить
SeedRnd MilliSecs()
Local SZ%=1000
Dim p(SZ)
Local secret=Rand(0,SZ)
Local J=0
For I=0 To SZ
    p(I)=J
    If I=secret
        J=J+2
    Else
        J=J+1
    EndIf    
Next
;===================
Local K#=SZ/4
Local CHK%=SZ/2
Local d%=0
Local f=False
While True

    If p(CHK)>CHK
        If d=1
            f=True
        EndIf
        d=-1
    Else
        If d=-1
            f=True
        EndIf
        d=1
    EndIf
    If f
        Exit
    EndIf
    CHK=CHK+d*K
    K=K/2
    
Wend
If d=1
    For I=CHK To SZ
        If p(I)<>I
            I=I-1
            Exit
        EndIf
    Next
Else
    For I=CHK To 0 Step -1
        If p(I)=I
            Exit
        EndIf
    Next
EndIf
DebugLog "secret="+I
DebugLog "check - "+secret
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Dream (02.09.2009)
Старый 03.09.2009, 12:42   #13
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,935 пользователей)
Ответ: Простенькая задачка)

Как изначально задумывалось, но вчера не написалось:
SeedRnd MilliSecs()
Local SZ%=10000
Dim p(SZ)
Local secret=Rand(0,SZ)
Local J=-1
For I=0 To SZ
    If I=secret
        J=J+2
    Else
        J=J+1
    EndIf
     p(I)=J
Next
;===================
Local K#=SZ/2
Local CHK%=SZ/2
Local d%=0
Local STP=1
While K>=1
    K=K/2
    DebugLog "step "+STP
    DebugLog "p("+CHK+")="+p(CHK)
    STP=STP+1
    If p(CHK)>CHK
        d=-1
    Else
        d=1
    EndIf
    CHK=CHK+d*K
    DebugLog "next chk="+CHK
    DebugLog "-------" 
Wend
DebugLog "abort"
DebugLog "----end binary"
DebugLog "CHK="+CHK
DebugLog "d = "+d
DebugLog "step "+STP
DebugLog "p("+CHK+")="+p(CHK)
If p(CHK)<>CHK
    CHK=CHK-1
EndIf
CHK=CHK+1
DebugLog "result = "+CHK
DebugLog "steps: "+STP
DebugLog "secret = "+secret
WaitKey()
лог для 10000 элементов:
step 1
p(5000)=5000
next chk=7500
-------
step 2
p(7500)=7501
next chk=6250
-------
step 3
p(6250)=6251
next chk=5625
-------
step 4
p(5625)=5626
next chk=5312
-------
step 5
p(5312)=5313
next chk=5156
-------
step 6
p(5156)=5157
next chk=5078
-------
step 7
p(5078)=5079
next chk=5039
-------
step 8
p(5039)=5040
next chk=5019
-------
step 9
p(5019)=5020
next chk=5009
-------
step 10
p(5009)=5009
next chk=5014
-------
step 11
p(5014)=5014
next chk=5016
-------
step 12
p(5016)=5017
next chk=5015
-------
step 13
p(5015)=5015
next chk=5016
-------
abort
----end binary
CHK=5016
d = 1
step 14
p(5016)=5017
result = 5016
steps: 14
secret = 5016
14 обращений к массиву (вместо 10000)
пропущенное число 5016
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Эти 5 пользователя(ей) сказали Спасибо impersonalis за это полезное сообщение:
alcoSHoLiK (03.09.2009), Dream (29.11.2009), Harter (26.09.2009), Reks888 (06.11.2009), Tadeus (04.09.2009)
Ответ


Опции темы

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

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

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задачка... Atomikc Visual Basic 10 09.11.2009 19:45
Простенькая визуализацияя Harter C++ 3 17.08.2009 21:17
2 задачки mudriy Загадки 14 26.11.2007 11:55
Задачка!!! Halk-DS 2D-программирование 60 29.01.2007 00:06
Задача SubZer0 Загадки 8 30.07.2006 16:33


Часовой пояс GMT +4, время: 17:43.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com