|
Математика Методы математического моделлирования, программирование математических концепций, роль математики в создании игр |
31.08.2009, 21:44
|
#1
|
быдло
Регистрация: 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
|
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
|
быдло
Регистрация: 05.08.2007
Сообщений: 1,435
Написано 614 полезных сообщений (для 1,489 пользователей)
|
Ответ: Простенькая задачка)
а без перебора всего масива?
|
(Offline)
|
|
01.09.2009, 10:36
|
#4
|
злобный флудер
Регистрация: 10.07.2007
Сообщений: 2,585
Написано 789 полезных сообщений (для 1,476 пользователей)
|
Ответ: Простенькая задачка)
в посте №2 перебор иднт только до того как находится 0
|
(Offline)
|
|
01.09.2009, 10:45
|
#5
|
|
Ответ: Простенькая задачка)
DimasSup
если учитывать ту информацию что ты предоставил - без перебора никак
|
|
|
01.09.2009, 11:29
|
#6
|
Зануда с интернетом
Регистрация: 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
|
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
|
Бывалый
Регистрация: 09.09.2006
Сообщений: 656
Написано 54 полезных сообщений (для 110 пользователей)
|
Ответ: Простенькая задачка)
а может при запись в масив, запомнить где ноль)
|
(Offline)
|
|
01.09.2009, 19:24
|
#9
|
Blitz's Shame !!
Регистрация: 31.03.2007
Сообщений: 3,639
Написано 832 полезных сообщений (для 2,013 пользователей)
|
Ответ: Простенькая задачка)
а может при запись в масив, запомнить где ноль)
|
жжешь !!
я загадал где ноль !! как ты угадаешь ?? перебор ??
|
(Offline)
|
|
02.09.2009, 16:27
|
#10
|
быдло
Регистрация: 05.08.2007
Сообщений: 1,435
Написано 614 полезных сообщений (для 1,489 пользователей)
|
Ответ: Простенькая задачка)
Да, я ошибся, место пропуска не заносится в масив, как написал импер. Способы решения?
|
(Offline)
|
|
02.09.2009, 16:56
|
#11
|
Зануда с интернетом
Регистрация: 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
|
Зануда с интернетом
Регистрация: 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)
|
|
Сообщение было полезно следующим пользователям:
|
|
03.09.2009, 12:42
|
#13
|
Зануда с интернетом
Регистрация: 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 за это полезное сообщение:
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
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, время: 07:30.
|