Модераторы: Poseidon

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [C++] Поиск числа в потоке данных, частота появления числа > 51% 
:(
    Опции темы
Gelos
Дата 30.4.2007, 14:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 21
Регистрация: 29.4.2007

Репутация: нет
Всего: нет
Собственно, если точно известно,  что в потоке данных, размером, эдак гигибайт, состоящим из чисел в 16-ом коде, одно из чисел встречается чаще других с вероятностью >51% Каков самый оптимальный способ найти это число, за минимальное время?

И второй момент, злостные операторы new и delete.
В моем случае, вышла ситуация, что не смотря на то, что с выделенной памятью уже не работаю, вызов оператора delete рушит программу начисто. Путем хитрых извращений, а именно, вторай раз выделил на тот же указатель память, и после этого удалил, что то типа:

ukaz = new char[razmer];
----- // работа с выделеной памятью
-----
ukaz = new char[razmer];
delete [] ukaz;

собственно вопрос, при таком методе действий, когда я вызываю delete то будет очищаться вся память? И на сколько я заметил, второе выделение памяти не затирает информацию хранящуюся после первого вызова new?  smile 

  
PM MAIL   Вверх
Xenon
Дата 30.4.2007, 15:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Участник Клуба
Сообщений: 1529
Регистрация: 12.4.2006

Репутация: 19
Всего: 50
Gelos, Нет, ты получаешь летучего голандца в виде нестертого первого блока памяти. Хотя система его потом должна подтереть, но .. .smile

Это сообщение отредактировал(а) Xenon - 30.4.2007, 15:07


--------------------
user posted image  
PM MAIL   Вверх
Gelos
Дата 30.4.2007, 15:23 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 21
Регистрация: 29.4.2007

Репутация: нет
Всего: нет
Xenon

то есть  после вызова delete почистится все?

Это сообщение отредактировал(а) Gelos - 30.4.2007, 15:23
PM MAIL   Вверх
Xenon
Дата 30.4.2007, 15:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Участник Клуба
Сообщений: 1529
Регистрация: 12.4.2006

Репутация: 19
Всего: 50
Gelos, я же тебе говорю - первый раз то, что ты выделил, уйдет в небытие, освободиться только та память, что ты последний раз выделил.


--------------------
user posted image  
PM MAIL   Вверх
Ln78
Дата 30.4.2007, 15:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 274
Регистрация: 25.11.2006

Репутация: нет
Всего: 15
Gelos, так конечно делать не имеет никакого смысла: ты просто выделил новую память, и её же освободил, т.е. ты просто заставил систему выполнить лишние действия и всё. Проблема в другом:
Цитата

delete рушит программу начисто

Этого быть не должно, скорее всего ты испортил выделенную память до попытки её освобождения. Если код не слишком большой - приведи его
PM MAIL   Вверх
Gelos
Дата 30.4.2007, 15:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 21
Регистрация: 29.4.2007

Репутация: нет
Всего: нет
Xenon, 
гм.. интересная ситуация. значит мой "летучий голандец"  остается жить в памяти.  А с  учетом что все в цикле выделяется, да ещё и при данном раскладе не удаляется... smile 

Цитата

Этого быть не должно, скорее всего ты испортил выделенную память до попытки её освобождения. Если код не слишком большой - приведи его


он большой.  к сожалению.  Но что то в мысли на счет порчи памяти есть. 

Это сообщение отредактировал(а) Gelos - 30.4.2007, 15:40
PM MAIL   Вверх
Xenon
Дата 30.4.2007, 15:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Участник Клуба
Сообщений: 1529
Регистрация: 12.4.2006

Репутация: 19
Всего: 50
Gelos, Если тот первый кусок должным образом не удаляется, значит ты его где-то попортил.
Да, остается жить, если у тебя, конечно, сборщика мусора не предусмотрено smile


--------------------
user posted image  
PM MAIL   Вверх
Gelos
Дата 30.4.2007, 16:23 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 21
Регистрация: 29.4.2007

Репутация: нет
Всего: нет
Xenon, 
ок. бум искать. одно место уже нашел. действительно попортил. Короче, в хорошем тоне, сколько раз вызвал, столько раз и освободил. хорошо. Вроде со вторым вопросом помогли. пасиб ^__^"
PM MAIL   Вверх
apook
Дата 30.4.2007, 16:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 794
Регистрация: 12.7.2006

Репутация: 10
Всего: 23
Цитата

Каков самый оптимальный способ найти это число, за минимальное время?

Это надо волнообразно циклом туда сюда
Метод придуманный дядей Шеллом в 50-х годах прошлого века
Код

#include<stdio.h>
#include<conio.h>

void main(void)
{
int i, j, c, q, E;
int a[ 10 ] = { 0, 1, 2, 10, 4, 5, 6, 7, 8, 9 };

E=a[ 0 ];
for( i=0, c=10, q=0; i<10/2; i++, c--, q++ )
{
    for( j=q; j<c; j++ )
         if( E<a[ j ] )
             E=a[ j ]; 

    for( j=c-1; j>q; j-- )
         if( E<a[ j ] )
             E=a[ j ];

    }

printf( "%d", E );
getch();
return;
}



Вот поправил конечно же 10/2 в условии т.е в два раза меньше проходов

Это сообщение отредактировал(а) apook - 30.4.2007, 20:34


--------------------
Мои руки из дуба, голова из свинца ну и пусть ...
PM MAIL   Вверх
maxim1000
Дата 30.4.2007, 17:46 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 24
Всего: 110
Цитата(Gelos @  30.4.2007,  14:56 Найти цитируемый пост)
одно из чисел встречается чаще других с вероятностью >51% Каков самый оптимальный способ найти это число, за минимальное время?

побитово: решаем независимо задачу нахождения каждого бита этого числа...
а сами проходы можно объединить в один...


--------------------
qqq
PM WWW   Вверх
sergejzr
Дата 30.4.2007, 18:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 11
Всего: 360
Модератор: Название темы не отражает ее суть, или несколько вопросов в одном топе!

Ознакомьтесь с правилами форума!:

http://forum.vingrad.ru/index.php?showtopic=96391


--------------------
Me.
FB.
LinkedIn.
ORCID.
YT.
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
Gelos
Дата 30.4.2007, 18:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 21
Регистрация: 29.4.2007

Репутация: нет
Всего: нет
maxim1000, 
Цитата

решаем независимо задачу нахождения каждого бита этого числа...

Мы не знаем что это за число. нам его определить нужно.
apook, 
А немного пояснить алгоритм, если не трудно?  Вложенные циклы "управляются " из главного. Массив из чисел. Только, на сколько я заметил, они там все по 1 экзмепляру. Плюс немного не понятно все таки система вложенности циклов. что там во что вложено?
PM MAIL   Вверх
apook
Дата 30.4.2007, 18:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 794
Регистрация: 12.7.2006

Репутация: 10
Всего: 23
Суть в следующем:
Есть количество цифер  которые надо проверить, это значит что надо
сверить каждое число со всеми числами массива.
Задача делать как можно меньше лишних движений

алгоритм Шелла (вообще это алгоритм сортировки), так вот он заключается в проходах взад вперед по массиву причем каждый раз
ко-во сравниваемых элементов уменьшается на один вконце и на один вначале т.к в них отпадает необходимость(ведь они уже проверены)

Если использовать вывод то это выглядит так:
Смотри внимательно:
Код

#include<stdio.h>
#include<conio.h>

void main(void)
{
int i, j, c, q;
int a[ ] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };


for( i=0, c=10, q=0; i<10; i++, c--, q++ )
{
    printf( "\n" );
    for( j=q; j<c; j++ )
    {
         printf( "%d ", a[ j ] );
         getch(); 
         }

    printf( "\n" );

    for( j=c-1; j>q; j-- )
    {
         printf( "%d ", a[ j ] );
         getch(); 
         }
    }

getch();
return;
}

 



--------------------
Мои руки из дуба, голова из свинца ну и пусть ...
PM MAIL   Вверх
Gelos
Дата 30.4.2007, 19:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 21
Регистрация: 29.4.2007

Репутация: нет
Всего: нет
apook, 
То есть мы берем элемент с начала и сравниваем его со всеми элементами из последовательности.. Хм, ладно, как сформулирую запрос, то напишу. Сейчас сразу безполезно. 
PM MAIL   Вверх
apook
Дата 30.4.2007, 19:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 794
Регистрация: 12.7.2006

Репутация: 10
Всего: 23
Имей ввиду это черновой вариант, его еще надо оптимизировать
так навскидку набросал....


--------------------
Мои руки из дуба, голова из свинца ну и пусть ...
PM MAIL   Вверх
maxim1000
Дата 30.4.2007, 20:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 24
Всего: 110
найдём старший бит числа
нам известно, что само число встречается > 51% (если я правильно понял)
значит значение его старшего бита встречается не меньше (даже, возможно, больше, т.к. такой же старший бит может оказаться и в других числах)
так что просто пробегаемся по всему массиву, смотрим на все старшие биты, кого больше 0 или 1
кого больше - то и является старшим битом искомого числа
аналогично можно найти остальные биты...


--------------------
qqq
PM WWW   Вверх
Gelos
Дата 30.4.2007, 22:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 21
Регистрация: 29.4.2007

Репутация: нет
Всего: нет
maxim1000, Благодарю, мессир,  этот алгоритм, тоже выглядит многообещающим.Есть над чем подумать.
PM MAIL   Вверх
Dov
Дата 30.4.2007, 23:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


аСинизатор
***


Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88
Если массив неотсортирован, то нужно сделать быструю сортировку. И искомое число будет иметь индекс N / 2 + 1, где  N - это размер массива. Всё.


--------------------
Тут вечности запах томительный,
И свежие фрукты дешевые, 
А климат у нас – изумительный, 
И только соседи – #уевые. 
                           Игорь Губерман.
PM   Вверх
Rockie
Дата 1.5.2007, 19:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1143
Регистрация: 23.4.2006

Репутация: 13
Всего: 31
Dov, 
Цитата(Gelos @  30.4.2007,  14:56 Найти цитируемый пост)
одно из чисел встречается чаще других с вероятностью >51%

{ 1, 0, 2, 0, 3, 0, 4, 5, 6, 7, 8, 9, 10 }




--------------------
Чтобы иметь большой гардероб - надо иметь большой гардероб.
PM   Вверх
Dov
Дата 1.5.2007, 20:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


аСинизатор
***


Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88
Rockie, 1 : 1.  smile 


--------------------
Тут вечности запах томительный,
И свежие фрукты дешевые, 
А климат у нас – изумительный, 
И только соседи – #уевые. 
                           Игорь Губерман.
PM   Вверх
Rockie
Дата 1.5.2007, 21:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1143
Регистрация: 23.4.2006

Репутация: 13
Всего: 31
Dov, в этом нет необходимости

 smile




--------------------
Чтобы иметь большой гардероб - надо иметь большой гардероб.
PM   Вверх
Страницы: (2) [Все] 1 2 
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0621 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.