VPF::[Алгоритм] Перестановка разрядов числа (перебор)

KasMP

Дата 7.12.2008, 10:52 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

Репутация: 1
Всего: 30

Silent, мне даже слов не хватает smile

Цитата(Silent @ 26.11.2008, 23:10

)

P.S. а все-таки я крут (маньяк, дурак, нужное подчеркнуть smile

)

Ну, видимо, все-таки совсем не дурак smile

, а вот кусочек маньяка (в хорошем смысле этого слова) очень даже может жить в тебе smile

Цитата(Silent @ 26.11.2008, 23:10

)

Я не стал сливать все в кучу для "только циклы и условия", оставлю как есть, с процедурами и функциями, для наглядности. Воспитание не позволяет.

Если бы ты все это еще объединил, то было бы совсем нечитаемо. Хорошо, что ты этого не сделал smile

.

В некоторых местах я не допоняла, где-то совсем не поняла smile

...

"inline"
Код
inline int
Код
inline bool

Это что за разновидность типа? Я знаю только 4 модификации, описанные в С89: signed, unsigned, short, long.
Пока я поняла только то, что "inline int" привязан или к Visual Studio (что разрешается в моем случае), или непосредственно к C++ (а у нас не весь С++, а только его хорошо известное подмножество). О существовании модификаций для "bool" я даже не подозревала (ну что можно там сделать? или 0, или 1... что можно там изменить?!?!).
Вообще насколько существенно для твоей программы то, что вместо "int" и "bool" используются "inline int" и "inline bool"?
Операторы "<<" и "|="
Я совсем не поняла, что делает функция
Код
inline bool Good(int y)

Особенно непонятны операторы "<<" и "|=". Как следствие, строки
Код
res = ((flag & (1<<(tmp%10))) == 0) & (tmp%10 != 0); flag |= (1<<(tmp%10));
очень сильно пугают.
"floor"
Код
int end = (int)floor(sqrt((double)x));

Сначала мы приводи х к типу double, потому что аргумент sqrt() обязан быть такого типа. Потом мы вычисляем корень. Потом ... . А потом все это снова приводим к int.
ЧТо должно быть на месте многоточия? И зачем вообще это надо?
Код
for (count = 1; tmp>0; tmp /=10, count++); int n_ = 1; for (int i=0;i<count-1;i++, n_ *= count);
Для числа из 3-х цифр мы получим 4^3, для числа из 4-х цифр - 5^4 и т.п.. В чем смысл? (размещения, перестановки?)

Надеюсь, что ты ответишь хотя бы на часть вопросов smile

.

Это сообщение отредактировал(а) KasMP - 10.12.2008, 22:13

KasMP

Дата 10.12.2008, 18:47 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

Репутация: 1
Всего: 30

Буду разбирать уже написанный код (за что большое человеческое спасибо автору smile

) и переписывать его без использования функций smile

...

Итак,

Цитата(Герберт Шилдт @ "Полный справочник по С++")

Несмотря на то что параметризованные макросы довольно полезны, в языке C++ есть более эффективный спсоб создания подствляемого кода, основанный на использовании ключевого слова inline.

mes

Дата 11.12.2008, 13:19 (ссылка)

(нет голосов)

Загрузка ...

любитель

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

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

Цитата(KasMP @ 7.12.2008, 10:52

)

inline

Это подсказка компилятору, сделать функцию встраиваемой (т.е просто куском кода, а не функцией). Выкинь ее и не забивай голову пока.

bool - это логический тип, может быть true (1) или false (0)
если числовой тип конвертируется в bool то 0 это false, все остальное есть true;

if (25) .. // выполнится условие так как 25 не ноль, а значит true
if (0) // не выполнится потому как условие false

Цитата(KasMP @ 7.12.2008, 10:52

)

Особенно непонятны операторы "<<" и "|=". Как следствие, строки

<<  >> это битовые сдвиги:
00001000 >> 2 = 00000010
00001000 << 1 = 00010000

b |= 1; аналогична b = b|1;
b &=1;                     b = b&1;

|| - логическое_или . Если один из аргументов true, то результат true
| -  побитовое_или .  то же самое что и логическое, но применительно к каждому бита аргумента:
т.е 11100011 | 00001111 = 11101111
для логических сравнений битовое представление не важно поэтому
true || false = true
22 || 0 = true

&& - логическое_и. Если оба аргумента true то результат true.
& - побитовое_и
т.е 11100011 & 00001111 = 00000011
true && false = false
22 && 0 = false

Цитата(KasMP @ 7.12.2008, 10:52

)

"floor"

Округляет x до ближайшего меньшего целого.

Это сообщение отредактировал(а) mes - 11.12.2008, 13:30

--------------------

http://opendots.net

mes

Дата 11.12.2008, 13:35 (ссылка)

(нет голосов)

Загрузка ...

любитель

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

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

! означает логическое_нет, а != соответсвенно не_равно,

Код


!true      = false
!0          = true
true!=false   =true
25!=12     = true
25!=25     = false
25==25    = true

Это сообщение отредактировал(а) mes - 11.12.2008, 13:37

--------------------

http://opendots.net

mes

Дата 11.12.2008, 14:31 (ссылка)

(нет голосов)

Загрузка ...

любитель

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

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

Цитата(KasMP @ 28.10.2008, 20:39

)

Но на самом деле мы же не знаем, сколько разрядов будет!!!

если известно максимальное кол-разрядов, то столько и циклов и делать. В случае нехватки разрядов циклы просто останутся вырожденными..

Цитата(KasMP @ 28.10.2008, 20:39

)

каждая цифра в полученном числе может встречаться не больше раз, чем в первоначальном.

а меньше значит может ?
например для числа 2221 верны ли такие "перестоновки" как 22, 21 и 212 ?

если да то подход с простой перестановкой не подходящее решение.

Цитата(KasMP @ 28.10.2008, 20:39

)

Если для числа из n разрядов ни одно полученное из n цифр число - не простое, то надо уменьшать кол-во участвующих цифр до (n-1) ; потом, если опять нет простого, уменьшать до n-2.

а при уменьшении какую цифры выкидывать, вначале в середине или конце ? ;)
тут тоже рождается перебор, который мпожно решить используя как помощник битовую комбинацию, о чем предлогал Silent.

Цитата(KasMP @ 28.10.2008, 20:39

)

В заданном натуральном числе выбрать некоторые цифры так, чтобы образованное ими число было максимальным простым числом.

максимально простое это с наименьшим количеством делителей ?

Это сообщение отредактировал(а) mes - 11.12.2008, 14:39

--------------------

http://opendots.net

mes

Дата 11.12.2008, 16:01 (ссылка)

(нет голосов)

Загрузка ...

любитель

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

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

удалено...

Это сообщение отредактировал(а) mes - 11.12.2008, 21:14

--------------------

http://opendots.net

KasMP

Дата 11.12.2008, 18:49 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

Репутация: 1
Всего: 30

mes, большое спасибо за желание помочь smile

. Приятно удивило smile

.

Вообще вчера я разобралась со всеми неизвестными операторами (только linear не до конца поняла, а просто удалила - из его описание понятно, что использовать его необязательно), сегодня утром - со смыслом каждой функции и вообще каждой строчки, кроме одной smile

.

Так и не удалось понять smile

...
Функция Good проверяет, а имеет ли смысл подстановка y. Чтобы подстановка в нашем случае была правильной, она не должна содержать одинаковых цифр (следует из условия "каждая цифра в полученном числе может встречаться не больше раз, чем в первоначальном"). Понятно, что мы (вернее, Silent) создает так называемый флажок, на котором отмечает те цифры-позиции, которые уже были (изящно отмечает smile

). Начинаем с первого разряда и доходим до последнего, пополняя флажок единичками... Если единичка хочет наложиться на единичку, то перестановка неправильная и все... Все логично smile

Код

res = ((flag & (1<<(tmp%10))) == 0) & (tmp%10 != 0);

Но причем здесь вторая часть условия smile

?? Почему бы числу-перестановке не содержать ноль???? Что в этом плохого?!

Цитата(mes @ 11.12.2008, 14:31

)

а меньше значит может ?
например для числа 2221 верны ли такие "перестоновки" как 22, 21 и 212 ?

Да, правильные перестановки.

Цитата(mes @ 11.12.2008, 14:31

)

а при уменьшении какую цифры выкидывать, вначале в середине или конце ? ;)

Все попеременно smile

Цитата(mes @ 11.12.2008, 14:31

)

максимально простое это с наименьшим количеством делителей ?

Нет

. Максимальное простое - это простое в самом обычном смысле этого слова (1,3,5,7,9,11,13,17,19,23,29,...), но самое большое по значению среди других доступных.
Например, в множестве {43; 139; 71; 223; 457} максимальным простым будет 457 (числа, имеющие хоть какие-нибудь делители, рассматривать не за чем).

Цитата(mes @ 11.12.2008, 16:01

)

вроде так, компилировать и тестировать не пробовал, так как времени не осталось, но по идеи должно перебирать все варианты для чисел не длинее 6 разрядов.
лишние скобки и такие бесмысленные операции как /1 поставил для наглядности..

Выглядит красиво smile

. Посмотрю попозже smile

mes

Дата 11.12.2008, 20:16 (ссылка)

(нет голосов)

Загрузка ...

любитель

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

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

Цитата(KasMP @ 11.12.2008, 18:49

)

Выглядит красиво smile smile . Посмотрю попозже smile .

не смотри... там много глупого кода..
вот переписал не используя битового представления... вроде полегче должно смотреться
проверил - вроде все комбинации находит
проверку на простоту оставил тебе для разминки )

Код


#include <iostream>

unsigned  pow10 (unsigned a) { unsigned base =1; for (unsigned i=0; i<a; ++i) base*=10; return base; }

int main()
{
unsigned value =127;  // условное число
// для начала узнаем длину числа (кол-во разрядов)
unsigned len=1;  // даже если число 0, длина равна 1
for (unsigned i=value; i>9; i/=10) ++len;

if (len>6) std::cout << "ERROR: value is too long!";
else
for (unsigned a6=0; a6<=((len>=6)?len:0); ++a6)
 for (unsigned a5=0; a5<=((len>=5)?len:0); ++a5)
  for (unsigned a4=0; a4<=((len>=4)?len:0); ++a4)
   for (unsigned a3=0; a3<=((len>=3)?len:0); ++a3)
    for (unsigned a2=0; a2<=((len>=2)?len:0); ++a2)
     for (unsigned a1=1; a1<=((len>=1)?len:0); ++a1)
     {
        //  отсечение если есть двойное использование одного и того же разряда
        if (a6 && (a6 == a5 || a6 == a4 || a6 == a3 || a6 == a2 || a6 == a1)) continue;
        if (a5 && (a5 == a4 || a5 == a3 || a5 == a2 || a5 == a1)) continue;
        if (a4 && (a4 == a3 || a4 == a2 || a4 == a1 )) continue;
        if (a3 && (a3 == a2 || a3 == a1 )) continue;
        if (a2 && (a2 == a1 )) continue;

        // отсечение разрывов
        if  ((!a1 && a2) || (!a2 && a3) ||(!a3 && a4) ||(!a4 && a5) ||(!a5 && a6)) continue;

        unsigned combival =0; // результат комбинации разрядов

        if (a1) combival += (value/pow10(a1-1) %10)*1;
        if (a2) combival += (value/pow10(a2-1) %10)*10;
        if (a3) combival += (value/pow10(a3-1) %10)*100;
        if (a4) combival += (value/pow10(a4-1) %10)*1000;
        if (a5) combival += (value/pow10(a5-1) %10)*10000;
        if (a6) combival += (value/pow10(a6-1) %10)*100000;

        // тестовый вывод
        std::cout <<combival << ", ";

        //  проверкa нa простоту числa
        // ...

     }

  std::cout <<  std::endl;
  system("pause");
  return 0;
}

примечание :
аn (a1,a2.. ) - показывает что в разряд n результата встанет разряд со значением переменной от исходника
то есть если а3 == 5 то в результате 3й разряд будет взят из 5го разряда источника.
если аn == 0 означает что разряд n не используется

Это сообщение отредактировал(а) mes - 14.12.2008, 17:02

--------------------

http://opendots.net

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »