forum.boolean.name

forum.boolean.name (http://forum.boolean.name/index.php)
-   Математика (http://forum.boolean.name/forumdisplay.php?f=85)
-   -   Простенькая задачка) (http://forum.boolean.name/showthread.php?t=9038)

Dream 31.08.2009 21:44
Простенькая задачка)
 
Задачка такая:
Есть последовательность чисел от 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. язык реализации значения не имеет

IGR 31.08.2009 22:01
Ответ: Простенькая задачка)
 
Код:
for(int i=1;i<1000;i++) {
if(arrInt[i] == 0) {
int res = i;
break;
}
}
как-то так...

Dream 01.09.2009 05:51
Ответ: Простенькая задачка)
 
а без перебора всего масива?

NitE 01.09.2009 10:36
Ответ: Простенькая задачка)
 
в посте №2 перебор иднт только до того как находится 0

jimon 01.09.2009 10:45
Ответ: Простенькая задачка)
 
DimasSup
если учитывать ту информацию что ты предоставил - без перебора никак

impersonalis 01.09.2009 11:29
Ответ: Простенькая задачка)
 
В формулировке нет ошибок? На месте пропуска 0 или разрыв типа: 1 2 4 5 ?

IGR 01.09.2009 13:21
Ответ: Простенькая задачка)
 
Цитата:
for(int i=0;i<1000;i++)
{
need_sum+=i;
have_sum+=arrInt[i];
}
эм... ну у тебя же тоже перебор !! ;)

Horror 01.09.2009 18:09
Ответ: Простенькая задачка)
 
а может при запись в масив, запомнить где ноль)

IGR 01.09.2009 19:24
Ответ: Простенькая задачка)
 
Цитата:
а может при запись в масив, запомнить где ноль)
жжешь !!

я загадал где ноль !! как ты угадаешь ?? ;) перебор ??

Dream 02.09.2009 16:27
Ответ: Простенькая задачка)
 
Да, я ошибся, место пропуска не заносится в масив, как написал импер. Способы решения?

impersonalis 02.09.2009 16:56
Ответ: Простенькая задачка)
 
бинарный поиск на базе критерия
m[i]!=i
m[i]<i
m[i]>i

impersonalis 02.09.2009 17:48
Ответ: Простенькая задачка)
 
на скорую руку - ногами не бить
Код:
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

impersonalis 03.09.2009 12:42
Ответ: Простенькая задачка)
 
Как изначально задумывалось, но вчера не написалось:
Код:
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


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

vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot