Есть числа, приблизительно сороказначные, из которых мне нужно составить число не превышающего шести знаков. Первое что пришло в голову, это разбить большое число на группы, по пять знаков и сложить - 91111+98106+10199+11632+79981+06101+99116+93 = 396339. Но я в математики не силён и поэтому хочу спросить - есть ли шансы, что конечное значение повторится? То есть, могут ли цифры в сороказначном числе распределится так, что результат повторится? И есть ли в математике, алгоритм для составления не повторяющихся ключей, созданных из чисел?

задан 12 Апр '14 16:11

Нужен алгоритм получения шестизначного (или меньше) числа, при этом для каждого сорокозначного было свое уникальное меньшее число? Это программно Вы будете реализовывать? Повториться могут, если возьмем, например, шестизначное число $%\overline{abcdef}$%, из которого надо составить трехзначное, то по Вашему алгоритму будет: $%\overline{ab}+\overline{cd}+\overline{ef}=\overline{xyz}$%,если число будет равно $%\overline{badcfe}$% или $%\overline{cdefab}$%, то результат будет одинаковый, при чем в Вашем случае таких чисел (изначально разных, но дающих одинаковый результат) будет довльно много.

(12 Апр '14 16:33) kirill1771

Еще вопрос: а Вы не можете поточнее интервал начальных чисел написать? От 35-значных до 40-значный, например.

(12 Апр '14 16:57) kirill1771

Интервал больших чисел колеблеться от 35 до 40 цифр. Реализовывать буду программно ( мне нужно ключ строку переделать в ключь int ). И да, мне нужно на каждое уникальное многозначное число, получить меньшее уникальное. И раз повторов не избежать, то Вы не знаете, существует ли какой-то проверенный алгоритм? Спасибо! И Вы наверное немного ошиблись, вот пример описанный Вами -12+34+56 = 102, 21+43+65 = 130

(12 Апр '14 17:05) shatal

@shatal: я не знаю алгоритмов токого рода, но могу предложить Вам свой, я точно не уверен, будет ли он работать во всех случаях (я на нем еще разные случаи проверю), но он гарантированно в разы уменьшит вероятность повтора.
Дано сорокозначное число, разбиваем его на "порции", например, по пять чисел (как Вы делали), я обозначу порции по буквами (каждую порцию отдельной буквой), допустим получились следующие наборы цифр:$%a,b,c,d,e,f,g,h$%, тогда можно из этих порций можно получить уникальное число таким способом: $%((((a+b)\times c+d)\times e+f)\times g+h $%.

(12 Апр '14 17:27) kirill1771

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

(12 Апр '14 17:29) kirill1771

@shatal: у Вас не объяснено, что значит "составить из". Если я правильно понимаю, Вы хотите найти удачную функцию, которая каждому 40-значному числу по какому-то закону (желательно, простому) сопоставляет 6-значное число. Понятно, что значения неизбежно будут повторяться -- по той причине, что 40-значных чисел намного больше. Тогда вопрос заключается в том, что именно Вы хотите построить. Тут возможны разные варианты -- скажем, мы можем желать, чтобы повторы происходили как можно реже, и так далее. Но избежать их совсем нельзя (по принципу Дирихле).

(12 Апр '14 18:04) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
2

@shatal: (пишу в ответе, так как больше нет возможности комментировать): тот минус, о котором я писал выше, можно обойти следующим образом:
$%(((((a$% mod $%b)+b)\times c+d)\times e+f)\times g+h $% - это избавляет от случая, когда сумма первых порций одинакова, а порции просто переставлены местами, но при этом еще не учитывает случай, если в порциях цифры разные, а суммы одна (например для трехзначных $%113, 437$% и $%143,407$% ), поэтому для каждой порции надо проделать тоже самое перед выполнением "главного процесса", то есть, если $%a$% состоит из цифр $%v,w,x,y,z$%, то для нее надо сначала сделать так: $%a=(((v $% mod $%w +w)\times x+y)\times z)$% и аналогично для $%b,c,d...$%, а после этого уже подставлять их значения в $%(((((a$% mod $%b)+b)\times c+d)\times e+f)\times g+h $%.

ссылка

отвечен 12 Апр '14 18:26

@kirill1771: Спасибо! Сейчас буду пробовать. Но у меня один маленький вопрос ( a mod b ) это ( a / b )?

(12 Апр '14 19:41) shatal

@shatal: это остаток от деления, например, $%17$% mod $%5=2$%, в нашем случае это остаток от деления на $%b$%. Во многих языках программирования эта функция так и называется.

(12 Апр '14 19:51) kirill1771

@shatal: действительно, если у Вас цель все еще - это однозначное преобразование из сороказначного в шестизначное уникальное число, то сделать это будет возможно максимум для $%N$% сорокозначных чисел, где $%N$% - максимальное шестизначное число (шесть девяток). Поясню: допустим нам из двузначные числа нужно преобразовать в уникальные однозначные, но у нас всего $%9$% (не считая нуля) однозначных, так что каким бы ни был алгоритм, все равно, если после девяти преобразований начнем преобразовывать числа еще, то полученные однозначные будут совпадать.

(12 Апр '14 20:00) kirill1771

@kirill1771: я понимаю, что закончатся. А Вы не скажете, если увеличивать длину конечных ключей, с шести до семи, восьми.. То Ваш пример будет работать, если добавить ещё одну пару букв в скобках?

(12 Апр '14 20:58) shatal

@shatal: да, будет, переменные можно добавлять сколько угодно по этому принципу: прибавить, умножить, прибавить, умножить ...

(12 Апр '14 21:00) kirill1771

Спасибо Большое!

(12 Апр '14 21:09) shatal

@kirill1771: у меня к Вам ещё несколько вопросов - 1) сколько минимум групп из пяти знаков может существовать для работоспособности? 2) Если ключи создавать из разных по длине групп ( первый ключ из пяти групп, второй из шести ), то повторы будут иметь место? 3) Возможно ли разные по длине групп последовательности, привести к минимально допустимой по длине групп и создать уникальный ключ? Если это выходит за рамки темы или уже нет место для комментариев, то удалите какой-нибудь пост скажите, что ответ есть ( если конечно у Вас есть время и желание ) и я создам новую тему. Спасибо!

(13 Апр '14 14:38) shatal

@shatal: 1)чисто теоретически можно вообще без групп, но там, вроде бы есть какой-то водвох (я вчера это продумывал, а сейчас вспомнить не могу, если вспомню, допишу), а так, две - минимум (можно не по пять знаков).
2)Да вероятность совпадения возрастает, но этим можно пренебрачь, она слишком медленно растет, хотя я над этим еще подумаю сейчас.
3) Не понял вопроса, можете уточнить (перефразировать как-то)?

(13 Апр '14 15:08) kirill1771
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×509

задан
12 Апр '14 16:11

показан
701 раз

обновлен
13 Апр '14 15:09

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru