powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как найти число
24 сообщений из 74, страница 3 из 3
Как найти число
    #36080294
vino
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
AlexandrPlusvinoAlexandrPlus[quot vino][quot AlexandrPlus]...так и в этой другого N не может быть...
здесь как раз N <= M и только поиском можно найти искомое число

тады, чтобы приладить алгоритм - можно расширить массив N до M+1, заполнив нулями, и когда в m[0] или
по порядку следования в m встретится 0, то просто брать в m[0] следующие число по порядку ОДНОГО прохода
по m

при этом остаемся в "линейном" времени

P.S. Хотя есть память ограничена, то - не пройдет.
вот-вот, поэтому и нужна БИТОВАЯ карта, ее размер будет минимален
перестановка, на самом деле, не считается дешевой операцией, и к тому же Вы захотели дополнительное условие проверять (на =0)
а то,что выделено, может привести к зацикливанию
...
Рейтинг: 0 / 0
Как найти число
    #36080313
vino
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
AlexandrPlus...можно расширить массив N до M+1, заполнив нулями, и...
вот главная идея - тогда, похоже, можно применить расчетную формулу
...
Рейтинг: 0 / 0
Как найти число
    #36080323
vino
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
точнее, я глюканул, - там же не будет последовательности
...
Рейтинг: 0 / 0
Как найти число
    #36080332
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Очень юный падаван пишет:

> Случайно к вам попал =)
> Но прям даже интересно стало. А как оцените такой код? Это джава,

Это хренотень какая-то а не джава. Ну да ладно.
Должно быть что-то типа

Код: plaintext
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.
32.
33.
import java.lang.*;
import java.util.*;

public class FindDouble
{

     static final int ELEMENTS_COUNT =  10000 ;

     static int[] elements = new int[ELEMENTS_COUNT];
     static Set<Integer> metElements = new HashSet<Integer>();

     public static void main(String args[])
     {
	for(int i =  0 ; i < ELEMENTS_COUNT; i++)
	    elements[i] = i;

	elements[ELEMENTS_COUNT/ 5 ] =  123 ;
	
	Integer doubledElement = null;
	for( int element : elements )
	{
	    if( metElements.contains(element) )
	    {
		doubledElement = new Integer( element );
		System.out.println("Found doubled element " + doubledElement.toString() );
	    }
	    else
	    {
		metElements.add( new Integer( element ) );
	    }
	}
     }
}

Код: plaintext
1.
2.
3.
ziv@xxx:~/tmp$ javac -Xlint:unchecked  FindDouble.java
ziv@xxx:~/tmp$ java FindDouble
Found doubled element 123

Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
Как найти число
    #36080336
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
> Очень юный падаван
> if((s = set.size()) == size){
> doubleValue = array[i];
> break;

Вот я и не понял, при чём тут размер какой-то.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
Как найти число
    #36080342
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
junior idiot пишет:

> такие ситуации обычно и возникают, потому и написали "линейное", но это
> нифига не значит что миллион любых чисел можно так взять и вставить в
> этот хешсет так же быстро как в массив.

Время -- линейное, но алгоритм не обладает в общем случае статистической
устойчивостью. Т.е. иногда может срываться. Хорошо, что ты кстати это
знаешь. Многие тупо думают что скорость поиска в хэш-таблице - строго
константа.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
Как найти число
    #36080359
Фотография VladConn
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Можно обратиться к массиву как к таблице через соответствующий SQL запрос.
Можно вместо массива использовать тот же словарь из библиотеки scripting (он не пропустит дупликат)....
...
Рейтинг: 0 / 0
Как найти число
    #36080365
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
MasterZiv

> Очень юный падаван
> if((s = set.size()) == size){
> doubleValue = array[i];
> break;

Вот я и не понял, при чём тут размер какой-то.
как я понял - если размер множества не изменился, то последнее вставленное число в нем уже было.
...
Рейтинг: 0 / 0
Как найти число
    #36080411
Фотография AlexandrPlus
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
vinoAlexandrPlusvinoAlexandrPlus[quot vino][quot AlexandrPlus]...так и в этой другого N не может быть...
здесь как раз N <= M и только поиском можно найти искомое число

тады, чтобы приладить алгоритм - можно расширить массив N до M+1, заполнив нулями, и когда в m[0] или
по порядку следования в m встретится 0, то просто брать в m[0] следующие число по порядку ОДНОГО прохода
по m

при этом остаемся в "линейном" времени

P.S. Хотя есть память ограничена, то - не пройдет.
вот-вот, поэтому и нужна БИТОВАЯ карта, ее размер будет минимален
перестановка, на самом деле, не считается дешевой операцией, и к тому же Вы захотели дополнительное условие проверять (на =0)
а то,что выделено, может привести к зацикливанию

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
while (M[ 0 ]<>M[M[ 0 ]])or(M[ 0 ]= 0 )
 do
 begin
 if M[ 0 ]<> 0 
   then
   begin
   MM:=M[ 0 ];
   M[ 0 ]:=M[M[ 0 ]];
   M[MM]:=MM;
   end
   else
   begin
   M[ 0 ]:=M[i];
   Inc(i);
   end;
 end;

ничего не зацикливается - и один проход (i)

перестановка (изменение указателей) вообще не дешевая,
но речь идет о "математическом" времени
...
Рейтинг: 0 / 0
Как найти число
    #36080456
Фотография AlexandrPlus
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
VladConnМожно обратиться к массиву как к таблице через соответствующий SQL запрос.


В "математическом" времени SQL-запрос в общем случае - комбинаторный перебор ведь, да ещё будет декартово произведение.
...
Рейтинг: 0 / 0
Как найти число
    #36080465
vino
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
AlexandrPlus
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
M[ 0 ]:= 0 ;
i:= 1 ; // пропуск нулевой итерации
while (M[ 0 ]<>M[M[ 0 ]])or(M[ 0 ]= 0 ) do
 begin
  if M[ 0 ]<> 0  then
   begin
    MM:=M[ 0 ];
    M[ 0 ]:=M[M[ 0 ]];
    M[MM]:=MM;
   end
   else
   begin
    M[ 0 ]:=M[i];
    Inc(i);
   end;
 end;
ничего не зацикливается - и один проход (i)...
один проход - слишком оптимистично сказано, так как ячейки, наполненные нулями, тоже начнут проверяться, а это уже не N ячеек
...
Рейтинг: 0 / 0
Как найти число
    #36080599
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Зив, а чем принципиально с точки зрения скорости работы отличается твой код на жабе от такой простой лабуды:

Код: plaintext
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>
#include <stdlib.h>
#include <time.h>


const int N =  100 ;
const int M =  1000 ;

int main()
{
     int i;
     int arr[N];
     int buffer[M];

     srand (time(NULL));

     for(i =  0 ; i < N; i++)
        arr[i] = (rand() % M) +  1 ;

     for(i =  0 ; i < N; i++)
     {
          if(buffer[arr[i]] ==  1 )
          {
               printf("First found duplicate is %i \n",arr[i]);
               break;
           }
           else
               buffer[arr[i]] =  1 ;
      }

	 return  0 ;
}

Ну понятно, твой HashTable будет занимать меньше места в памяти. Ну ты вроде на память забил и делал упор на быстродействие. Так этот вариант ещё и побыстрее будет, бо хэши то вычислять нэ трэба...
...
Рейтинг: 0 / 0
Как найти число
    #36080637
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
miksoft пишет:

> как я понял - если размер множества не изменился, то последнее
> вставленное число в нем уже было.

Вау, какие полёты мыслей ! А я и недопёр ! А по-простому
нельзя было ?
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
Как найти число
    #36080645
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mikhail_n пишет:

> Зив, а чем принципиально с точки зрения скорости работы отличается твой
> код на жабе от такой простой лабуды:

В общем-то ничем, если не учитывать, что твой код не работает
(не инициализируется массив buffer[M]). А так -- массив -- частный
случай хэш-таблицы. Только памяти жрёт больше, как ты и заметил.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
Как найти число
    #36080661
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Работает
...
Рейтинг: 0 / 0
Как найти число
    #36080774
Фотография AlexandrPlus
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
vinoAlexandrPlus, очевидно, что когда N = M+1, задача вырождается в расчетную: искомое число = сумма элементов -сумма арифметической последовательности (1,2,..,M)

А мне подумало - вспоминая то, когда в ВУЗе программировали голые процессоры - программа из 0 и 1: то есть программируя, невольно думаешь как машина Тьюринга - вычисления гораздо более затратны, чем сравнения ячеек и смещения с ячейки на ячейку.

А генетические алгоритмы - для задач оптимизации оказываются более эффективны, чем расчетные.
...
Рейтинг: 0 / 0
Как найти число
    #36080917
студентик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
alusovПодскажите правильный алгоритм. Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно число в этом массиве повторяется два раза.
Как найти число за наименьшее время.

Хм... По-моему, условие несколько неполное. Не раскрыто какие вспомогательные структуры данных разрешается использовать массивы, множества, либо, вообще, задача должна быть решена "на месте" без затрат памяти, т.е. используя только исходные данные ну и миниум переменных(индексы, буфер и прочее). В случае решения "на месте" думаю только сортировка поможет...
...
Рейтинг: 0 / 0
Как найти число
    #36080940
Фотография AlexandrPlus
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
грешок есть
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
i:= 0 ;
while (M[ 0 ]<>M[M[ 0 ]])or(M[ 0 ]= 0 ) do
 begin
  if M[ 0 ]<> 0  then
   begin
    MM:=M[ 0 ];
    M[ 0 ]:=M[M[ 0 ]];
    M[MM]:=MM;
   end
   else
   begin
    M[ 0 ]:=M[i];
    M[i]:= 0 ;
    Inc(i);
   end;
 end;
...
Рейтинг: 0 / 0
Как найти число
    #36081582
MasterZiv
Вау, какие полёты мыслей ! А я и недопёр ! А по-простому
нельзя было ?

Ну, мы уже выяснили, что на добавление уходит время, зависящее от количества элементов. Думаю, что время поиска элемента имеет ту же зависимость. А вот проверка размера, имхо, есть операция по времени фиксированная и более дешевая =) Собственно, руководствовался только этими соображениями.
...
Рейтинг: 0 / 0
Как найти число
    #36081732
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Очень юный падаван пишет:

> Ну, мы уже выяснили, что на добавление уходит время, зависящее от
> количества элементов. Думаю, что время поиска элемента имеет ту же

Во-первых, вставка в хеш-таблицу -- те же O(1).
Во-вторых, тебе вставлять-то в таблицу всё равно надо.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
Как найти число
    #36081750
MasterZiv
Во-первых, вставка в хеш-таблицу -- те же O(1).
Во-вторых, тебе вставлять-то в таблицу всё равно надо.

Я просто объяснял, почему проверял размер, а не делал проверку вхождения элемента в множество. То, что элемент в множество надо вставить - даже не обсуждается. А вот проверить размер - дешевле чем найти вхождение элемента.
...
Рейтинг: 0 / 0
Как найти число
    #36081763
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
MasterZiv
Очень юный падаван пишет:

> Ну, мы уже выяснили, что на добавление уходит время, зависящее от
> количества элементов. Думаю, что время поиска элемента имеет ту же

Во-первых, вставка в хеш-таблицу -- те же O(1).
Во-вторых, тебе вставлять-то в таблицу всё равно надо.

Он делает add + проверку размера, это вдвое дешевле, чем contains + add, если только HashSet не кэширует findPos(), а он его, судя по найденным исходникам, не кэширует.
...
Рейтинг: 0 / 0
Как найти число
    #36201290
HolyGun
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Код: plaintext
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.
32.
33.
34.
35.
36.
37.
38.
39.
program p2;

{$APPTYPE CONSOLE}

const
  n =  15 ;
  m =  25 ;

var
  a: array[ 1 ..n] of LongWord = ( 5 ,  6 ,  7 ,  8 ,  9 ,  17 ,  2 ,  3 ,  4 ,  11 ,  7 ,  13 ,  25 ,  20 ,
     24 );

procedure FindDupe;
var
  p: LongWord; //address of bitmap
  s: LongWord; //size of bitmap
  i: LongWord;
begin
  s := m div  8 ;
  if m mod  8  <>  0  then
    Inc(s);
  p := LongWord(GetMemory(s));
  for i :=  1  to n do
    begin
      if (PByte(p + (a[i] div  8 ))^ shr (a[i] mod  8 )) and  1  =  0  then // if bit number a[i] is not set then ...
        Inc(PByte(p + (a[i] div  8 ))^, ( 1  shl (a[i] mod  8 ))) // ... set the bit.
      else // the bit number a[i] has already been set.
        begin
          Writeln('Duplicate element is: ',a[i]);
          Break;
        end;
    end;
  FreeMemory(Pointer(p));
end;

begin
  FindDupe;
  Readln;
end.

Ответы на 1 (поиск нулевых битов) и 3-е задания (поиск дубликатов файлов) у мну тоже есть, могу выложить. Один хрен не взяли
...
Рейтинг: 0 / 0
Как найти число
    #36249137
Dellon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
HolyGun,
Если не сложно выложи решения задачи 1 и 3 на Делфе. Большое спасибо
...
Рейтинг: 0 / 0
24 сообщений из 74, страница 3 из 3
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как найти число
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]