Помогите составить алгоритм преобразования

Тема в разделе "C/C++/C#", создана пользователем Chrek625, 10 янв 2011.

  1. Chrek625

    Chrek625 Гость

    Есть массив
    Код (C++):
    char model[] = "1234567";
    а так же массив
    Код (C++):
    char test[7];
    в нескольких циклах я перебираю через индекс 2 массива все элементы 1 массива тоесть
    зарание указанно
    Код (C++):
    temp[0] = model[0];
    temp[1] = model[0];
    temp[2] = model[0];
    temp[3] = model[0];
    и в условие цикла указанно что как только первый элемент 2 массива полностью по очереди пройдет все элементы 1 массива то 2 элемент увеличивается на один элемент, а когда второй элемент дойдет до последнего элемента 1 массива на один элемент увеличивается значение 3 элемента ну вообщем вот чт получается
    Код (PHP):
    1111
    2111
    3111
    4111
    5111
    6111
    7111
    1211
    2211
    ...
    7211
    1311
    2311
    ...
    7311
    1411
    ...
    1511
    ...
    7511
    ...
    1611
    2611
    ...
    7711
    1121
    2121
    ...
    4771
    5771
    6771
    7771
    1112
    2112
    3112
    4112
    и так далее.

    как вы понимаете что каждая комбинация цифр есть определённый номер
    то есть к примеру у получившейся комбинации 1111 будет под номером 1
    2111 под номером 2 а у строчки 1211 номер 8 и так далее,
    но вот помогите придумать алгоритм при котором можно будет определить какая комбинация будет например под номером 300, но при этом не проходя все циклы?
    То есть можно ли как то зная все параметры к используемые в цикле высчитать что получится на определенной строчке? (то есть как узнать что на 300 строчке будет комбинация 6171 при моих условиях циклов не проходя все мои циклы?) Если можно то как?
    Заранее извиняюсь если вопрос глупый или плохо объяснил чего хочу...
     
  2. alik86

    alik86 Lotus team
    Lotus team

    Регистрация:
    20 ноя 2008
    Сообщения:
    465
    Симпатии:
    0
    Есть твёрдое убеждение, что можно вывести некую формулу зависимости x=f(k), где x - число в строке k, k - номер строки. Для вывода таких формул используются методы математической индукции (если мне не изменяет память).
    P.S. Чуть позже может быть вспомню своё олимпиадное детство и выведу формулу... но не факт :)
     
  3. hosm

    hosm * so what *

    Регистрация:
    18 май 2009
    Сообщения:
    2.450
    Симпатии:
    7
    может, привязаться к 7ричной системе счисления? Т.е. каждой из цифр "1234567" сопоставить 7ричные цифры "0123456"
    Переводим N-1 (т.к. цифры в примере нумеруются с 1) в 7ричную систему и записываем 7ричные цифры в обратном порядке. Потом обратное сопоставление ("0123456" сопоставить "1234567")
    Пример:
    N=300
    N-1 = 299 = 5+ 0* 7 + 6*49 + 0* 343
    Т.е. получаем 299 [10e] = 0605 [7e] (т.е. 299 [sub]mod10[/sub] =0605 [sub]mod7[/sub])
    Переворачиваем (реверс) 0605 в 5060. (Тут реверс используется, потому что в примере увеличение значений идет со старших цифр, т.е. быстрее растут цифры слева, а не справа)
    Затем цифры в 5060 "0123456" меняем соответственно на "1234567" и получаем 6171
     
  4. alik86

    alik86 Lotus team
    Lotus team

    Регистрация:
    20 ноя 2008
    Сообщения:
    465
    Симпатии:
    0
    Кстати, вспомнив про существование mod7 (под mod7 понимаем остаток от деления числа на 7 - в С/С++ оператор % кажется), а так же прикрутив целочисленное деление, оператор сравнения с 7 и модное слово рекурсия довольно не сложно находится номер прохода, вычисляется номер разряда, который увеличивается в данном проходе, его конкретное значение на данном шаге, номера разрядов, которые уже на максимуме (равны 7) и те, которым еще лишь предстоит на этот максимум выходить (равны 1).
    P.S. У OKEN явно решение посерьезнее, но такое еще и вспомнить надо -- лично для меня давно существуют лишь системы счисления, представленные в калькуляторе и то не все... :)
     
  5. hosm

    hosm * so what *

    Регистрация:
    18 май 2009
    Сообщения:
    2.450
    Симпатии:
    7
    alik86 насчет систем счисления - ограничиваться только калькулятором - это зря =)
    и да, кажется, мы примерно об одном и том же алгоритме :) только он у меня более формально описан... Ведь для перевода в 7ричную систему надо делить на степени 7ки =)

    Добавлено: т.е. я бы сразу получала в обратном порядке цифры 7ричного представления числа, увеличивала их на 1 и записывала в результат
     
  6. alik86

    alik86 Lotus team
    Lotus team

    Регистрация:
    20 ноя 2008
    Сообщения:
    465
    Симпатии:
    0
    Да, да, да - те же яйца, вид сбоку.
    Я почти мозг сломал, пока вспомнил правила перевода из одной системы в другую. Видели б меня мои институтские преподаватели - гордились бы, видели б лицейские учителя - сгорели бы со стыда... :)
     
  7. Chrek625

    Chrek625 Гость

    alik86
    OKEN
    Спасибо что откликнулись.
    Но OKEN а можно не большой код привести? сложновато вы описали для моего понимания, по коду было бы проще разобраться...
    И вопрос переводить числа в 7 систему в не зависимости от того сколько используется цифр?
     
  8. hosm

    hosm * so what *

    Регистрация:
    18 май 2009
    Сообщения:
    2.450
    Симпатии:
    7
    alik86 ну, честно признаюсь - я выше 7 в кубе на калькуляторе считала. И при этом осмеливаюсь ругать дочек, что они пользуются калькулятором при решении школьного д/з =)
    А именно из школы помню, что нас учили переводу в двоичную систему. Может, 8 или 16ричную тоже учили, но моя память о школе об этом ничего ваще не помнит :ya_lamo: Все остальное дал универ, и даже работа это из башки пока не выветрила...
    А большинство преподавателей не настолько наивны и даже не надеются, что студенты что-то вспомнят после экзамена =)
    вопрос непонятен. сколько используется цифр где?
    Что непонятно? Смотри. По заданию комбинация состоит из "1234567" - тут всего 7 цифр. И алгоритм получения чисел последовательный с увеличением цифр разрядов слева, поэтому взята семиричная система, только по правилам там цифры от 0 до 6 и увеличение разрядов справа...
    Количество разрядов в полученной комбинации в общем случае зависит от того, какую по счету комбинацию мы хотим получить.
    Для оптимизации можете записать степени 7ки в какой-то массив.
    1) Спрашиваете у юзера N. Проверяете на вхождение в диапазон [1.. 7[sup]m[/sup]].

    В примере m=4 - используется только 4 разряда (получаются комбинации 1111-7777, используется диапазон N от 1 до 7^4, включая граничные значения, ^ - это возведение в степень, т.е. pow() в терминах с++) Т.е. на основании N у нас в общем случае определяется m - число разрядов в полученной комбинации.
    2) уменьшаем число на 1
    k=N-1
    3а) получение последовательности цифр N-й комбинации в массив цифр
    Код (LotusScript):
    redim c(1 to m) As Byte ' выделяем память под массив цифр числа
    ' цикл получения всех цифр
    for i=m-1 to 0 step -1

    с(i+1) = k \ (7^i) + 1 ' частное при целочисленном делении числа на 7 в степени i увеличивается на 1 (переход от цифр 0..6 к цифрам 1..7)
    k = k mod (7^i) ' остаток от деления числа на 7 в степени i
    next
    в конце цикла получается с(1)с(2)...с(m-1)с(m) - цифры полученной N-й комбинации
    или
    3б) получение последовательности цифр N-й комбинации в строку
    Код (LotusScript):
    s=""
    for i=m-1 to 0 step -1
    s = Trim$(Str$(k \ (7^i) + 1)) & s ' цифра переводится в строку (частное от целочисленного деления числа на 7 в степени i + 1) и дописывается в начало строки-результата
    k = k mod (7^i) ' остаток от деления числа на 7^i
    next
    в конце цикла строка s содержит цифры полученной N-й комбинации
    (Так как в данный момент пишу на lotusscript, а не javascript, ловите пример получения N-комбинации не на с++, а на лотусскрипте с комментами - просто для пояснения алгоритма)
     
  9. Chrek625

    Chrek625 Гость

    OKEN
    а если в первом массиве не цифры а к примеру буквы
    Код (C++):
    char model[] = "abcdefghijklm";
    То предложенный вами вариант не подходит?
     
  10. hosm

    hosm * so what *

    Регистрация:
    18 май 2009
    Сообщения:
    2.450
    Симпатии:
    7
    Почему? "abcdefghijklm" соответствует "0123456789ABC" и вместо 7 используется 13
     
  11. Chrek625

    Chrek625 Гость

    OKEN
    А вы можете просто цифрами написать как вы получили 0605, просто цифрами что на что делили и так далее, просто у меня не сходится, и не получается ничего сделать;) хотя очень нужно...
     
  12. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Код (C++):
    #include <iostream.h>

    int main()
    {
    for ( int i = 0; i < 20; i++ ) {
    int k = i;
    for ( int j = 0; j < 4; j++ ) {
    cout << k % 7 + 1;
    k /= 7;
    }
    cout << endl;
    }
    return 0;
    }
    Тут без массивов. Если нужны массивы - объяви их, и записывай цифру в массив по индексу j.
     
  13. Chrek625

    Chrek625 Гость

    lazybiz
    Спасибо, но вы наверное не дочитали до конца мой первый пост, мне нужно зная номер строчки определить что в ней находиться.
     
  14. Shamil1

    Shamil1 Гость

    Люди, не стоит помогать этому муд*ку (нехорошему человеку), он весь рунет тритирует, сам думать не хочет, так ещё и не сообщает всю картину и наработки.
    А натолкнули его на путь истинный уже ни один и ни два раза:
    http://forum.vingrad.ru/act-Print/client/p...1/t-320184.html
    http://forum.antichat.ru/threadedpost25146...tml#post2514642
    http://forum.k0d.cc/showthread.php?t=9251
    https://rdot.org/forum/showthread.php?p=12605
     
  15. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Читал до конца. Именно поэтому я тебя только подтолкнул, а не писал весь код целиком.
    В моем коде переменная i - это и есть твой номер строки.
     
  16. Chrek625

    Chrek625 Гость

    lazybiz
    Ну тогда извиняюсь, не понял вашего толчка, ну вообщем то, это уже и не важно, спасибо что не остались в стороне.
     
Загрузка...

Поделиться этой страницей