Перейти из форума на сайт.

Новости • Файловые архивы
Поиск • Активные темы • Топ лист
Правила • Кто в on-line?
Вход • Забыли пароль? • Первый раз на этом сайте? • Регистрация
Компьютерный форум Ru.Board » Компьютеры » Прикладное программирование » Алгоритмы

Модерирует : ShIvADeSt

 Версия для печати • Подписаться • Добавить в закладки
Страницы: 1 2 3 4 5 6 7 8 9 10 11

Открыть новую тему     Написать ответ в эту тему

akaGM

Platinum Member		Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
все вопросы по алгоритмам, их созданию и сопровождению без привязки к какому-нибудь конкретному языку программирования...
ну или с привязкой :)
дать идею, помочь с математикой или, если вам не помогли в профильном топе...
 
по возможности используйте псевдокод в своих сообщениях
 
ссылки
 
  •  "ebook'и -- сборники алгоритмов"
     

    только помните, что тут никто ничего _делать за вас_ не обязан!
    для этого есть специальные места со своими ценами...
    • Всего записей: 24120 | Зарегистр. 06-12-2002 | Отправлено: 09:28 16-12-2016 | Исправлено: akaGM, 09:03 12-07-2019
    r u b o a r d m a n



    BANNED    		Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
    Всех с наступающим НГ!
     
    У меня такой вопросик, может кто сталкивался.  
     
    Требуется составить программу по решению уравнения с четырьмя неизвестными. Для чего это нужно.
     
    Собственно задача очень просто решается прямым перебором
     
    НО! такой способ решения приемлем только для ПК, где скорость вычислений достаточна
    для решения подобных задач.
     
    Существует ли алгоритм решения задачи, приемлемый для использования на мобильных
    устройствах    , не имеющих столь мощных вычислительных возможностей?
     
    PS Готовое решение для ПК, может кому сгодится:
    http://forum.ru-board.com/topic.cgi?forum=5&bm=1&topic=50071#1
     
    Всем спасибо за любую помощь!
    Всего записей: 484 | Зарегистр. 10-09-2014 | Отправлено: 17:30 31-12-2018 | Исправлено: r u b o a r d m a n, 17:36 31-12-2018
    ne_viens

    Advanced Member    		Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
    В телефонах вычислительно-ёмкий код обычно переносят в нативные *.so библиотеки.
    Всего записей: 1530 | Зарегистр. 01-11-2004 | Отправлено: 18:41 31-12-2018
    Mavrikii

    Platinum Member    		Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
    r u b o a r d m a n
    1) зачем от 5 до 99, если вы знаете возможный набор чисел
    2) в случае x * y если x меняется от 5 до 99, а перемена множителей ничего не меняет, то y можно менять от x + 1 (если x != y) до 99 (ну или аналогично только фиксированные значения из массива)
    3) раз есть значение u, то одну переменную можно считать (а не перебирать) из выражения и проверять сначала на целочисленность, а затем есть ли она в нужных значениях.
    Всего записей: 15118 | Зарегистр. 20-09-2014 | Отправлено: 18:54 31-12-2018 | Исправлено: Mavrikii, 18:56 31-12-2018
    r u b o a r d m a n



    BANNED    		Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
    Mavrikii

    Цитата:
    1) зачем от 5 до 99, если вы знаете возможный набор чисел  
    Жестко не стал задавать , потому как это связано с переменным набором чисел (сменный набор шестерен на разных станках разный, но у всех в пределах от 5 до 99). Поэтому так. Но то такое, к сути вопроса не сильно относится.

    Цитата:
    2) в случае x * y если x меняется от 5 до 99, а перемена множителей ничего не меняет, то y можно менять от x + 1 (если x != y) до 99 (ну или аналогично только фиксированные значения из массива)  
    Там есть проверка на повторы:
    Код:
     if( (ai!=bi)&&(ai!=ci)&&(ai!=di)&&(bi!=ci)&&(bi!=di)&&(ci!=di) )  
    Поэтому тупо перебор, и если нет уход на след. цикл - так проще. Но в заданном случае повторы надо будет отслеживать как-то по другому. Все будет зависеть от предложенного нового алгоритма решения задачи.
     

    Цитата:
    3) раз есть значение u, то одну переменную можно считать (а не перебирать) из выражения и проверять сначала на целочисленность, а затем есть ли она в нужных значениях.
    Отсюда поподробнее:  
     
    Из постановки задачи мы имеем уравнение:
    (a * c)/(b * d) = u
    u - известное.
    a, b, c, d - неизвестные.
     
    Каким образом
    Цитата:
    одну переменную можно считать
    ?
     
     
     
    Добавлено:
    ne_viens
    Цитата:
    В телефонах вычислительно-ёмкий код обычно переносят в нативные *.so библиотеки.
    Задача ставится для моделей поддерживающих Java2ME MIDP 2.0 CLDC 1.1 - это устаревшие модели уроня Nokia 40-й серии.
    Всего записей: 484 | Зарегистр. 10-09-2014 | Отправлено: 19:26 31-12-2018
    Mavrikii

    Platinum Member    		Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
    r u b o a r d m a n

    Цитата:
    Там есть проверка на повторы

    вы не поняли о чем я написал. я написал о сокращении циклов в два раза для каждой пары

    Цитата:
    Каким образом  

    a = u / c * b * d
    Всего записей: 15118 | Зарегистр. 20-09-2014 | Отправлено: 20:07 31-12-2018
    r u b o a r d m a n



    BANNED    		Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
    Mavrikii
    Цитата:
    a = u / c * b * d  
    так наверное точнее будет:
    a = ((b * d) * u) / c

    Цитата:
    о сокращении циклов в два раза
    та вобщем то я об этом думал, но все равно много вариантов просчитывать.
    Вобщем мне пришла идейка произведения (a * c) и (b * d) посчитать заранее.
    Накидал тут софтину что называется на коленке, для подсчёта всех вариантов перемножения, исключая повторы. Ууупс - встречаются повторы, причем дофига.
     
    Получилось 43 * 43 = примерно 1849 вариантов. Ну а теперь если прикинуть что их надо скомбинировать для подбора значения u - то получится 1849 * 1849 = где-то 3418801 вариантов.
     
    Все равно много, думаю Java ME такое не потянет.
     
    Щас надо подумать как бы изменить софтину чтоб без повторов получалось.
    Всего записей: 484 | Зарегистр. 10-09-2014 | Отправлено: 20:39 31-12-2018 | Исправлено: r u b o a r d m a n, 20:53 31-12-2018
    Alex_Piggy

    Advanced Member    		Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
    Доброе время, r u b o a r d m a n
    Немного другая форма  (a*c)/(b*d)=u
    1. Произведение a*с каждый раз считать не надо.  
    2. Для b можно посчитать границы - какое оно может быть максимальное - при d = 5 и минимальное - при d = 100. За эти границы выходить смысла нет.
    3. d не перебираем - считаем как (a*c)/(b*u). И смотрим расстояние до целого. Если устраивает - то печатаем.
    На awk - считает за 1 с.

    Код:
     
    {
      u=0.184584124
      maxi = 100
      for (a=5;a<100;a++) {
        for (c=5;c<100;c++) {
          ac = a*c;
          bmin= ac/(100*u)
          bmin = bmin > 5 ? int (bmin) - 1 : 5;  
          bmax= ac/(5*u)
          bmax = bmax < 100 ? int (bmax) + 1 : 100;
          for (b=bmin;b<bmax;b++) {
            d = ac/(b*u);
            dd = d-int(d)
          if (dd < 0.01 && dd > -0.01) print "d=" d  " c= "  c   " b= "  b  " a= " a ;
          }
        }
      }
    }
     
    Всего записей: 1891 | Зарегистр. 07-08-2002 | Отправлено: 20:52 31-12-2018
    r u b o a r d m a n



    BANNED    		Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
    Alex_Piggy
    Цитата:
    1. Произведение a*с каждый раз считать не надо.  
    А откуда мы его будем брать? Из головы чтоли?

    Цитата:
    if (dd < 0.01 && dd > -0.01)
    Там пределы точности по 0.00005 и меньше, так что ..
     
    с u=0.184584124 получаем:

    Цитата:
    Формула: (a*c)/(b*d) = 0.184584124
    Набор шестерен гитары:
    20,20,23,24,25,25,30,33,34,35,37,40,41,43,45,47,48,50,53,55,57,58,59,60,61,62,65,67,70,71,73,75,79,80,83,85,89,90,92,95,97,98,100
    a=70      b=89      c=23      d=98      /0.0000066/
    a=70      b=98      c=23      d=89      /0.0000066/

     
    где /0.0000066/ - допустимая разница между левой и правой сторонами уравнения, в пределах точности 0.00005
    Всего записей: 484 | Зарегистр. 10-09-2014 | Отправлено: 21:07 31-12-2018 | Исправлено: r u b o a r d m a n, 22:52 31-12-2018
    Alex_Piggy

    Advanced Member    		Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
    r u b o a r d m a n

    Цитата:
    1. Произведение a*с каждый раз считать не надо.
    А откуда мы его будем брать? Из головы чтоли?

    Кстати, не ac=a*c, а acu=a * c / u
    Посчитать один раз и потом использовать это значение в вложенном цикле с c, а не каждый раз вычислять это произведение.
    Это немного позволит уменьшить количество вычислений.
     

    Цитата:

    Цитата:
    if (dd < 0.01 && dd > -0.01)  

     Там пределы точности по 0.00005 и меньше, так что ..

    Так что можно поставить устраивающую Вас точность и посмотреть в списке - какие варианты Вас устроят
    Но да, awk не годится. Java, да?
    Всего записей: 1891 | Зарегистр. 07-08-2002 | Отправлено: 21:14 31-12-2018 | Исправлено: Alex_Piggy, 21:16 31-12-2018
    r u b o a r d m a n



    BANNED    		Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
    Alex_Piggy
    Цитата:
    3. d не перебираем - считаем как (a*c)/(b*u).
    В итоге d все равно придется подбирать. Поскольку с первого раза можно и не попасть в нужное значение d. Так что, от чего ушли к тому и пришли.
     
     
    Добавлено:
    Alex_Piggy
    Цитата:
    Посчитать один раз a * c / u
    Не выйдет. u - величина которую следует учитывать как переменную, из-за чего и вся канитель.
     
    Скачайте софт, там есть функция рассчёта произвольной гитары, и всё поймёте.
    Всего записей: 484 | Зарегистр. 10-09-2014 | Отправлено: 21:19 31-12-2018 | Исправлено: r u b o a r d m a n, 22:52 31-12-2018
    Alex_Piggy

    Advanced Member    		Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
    r u b o a r d m a n

    Цитата:
    Не выйдет. u - величина которую следует учитывать как переменную, из-за чего и вся канитель.
    Скачайте софт [?], там есть функция рассчёта произвольной гитары, и всё поймёте

    Внутри циклов подбора u меняется или нет? В том коде, что Вы давали - нет, не меняется. http://al-vo.ru/mekhanika/nastrojka-gitary-differenciala.html прочитал. Там тоже не меняется -  

    Цитата:
    После этого необходимо выбрать из набора такие четыре шестерни с числами зубьев Z1, Z2, Z3 и Z4, чтобы, установленные в гитару дифференциала, они образовали редуктор с передаточным отношением (u’) максимально близким к рассчитанному значению (u)

    Раасчитывается u, на его основе - подбираются a b c d. Верно?

    Цитата:
    В итоге d все равно придется подбирать

    Если в данный момент времени известна формула u = (a*c)/(b*d) и известны: a,b,c и u (неизвестно только d)  - надо ли перебирать d или это уравнение с одним неизвестным? И уже если d близко к целому - рассчитывать "допустимая разница между левой и правой сторонами уравнения, в пределах точности 0.00005"
    Да, и чтобы не было повторов - b не может быть меньше a. То есть  
    bmin = bmin > a ? int (bmin) - 1 : a;
    Хо-хо-хо
    Upd: Sorry, не  "b не может быть меньше a", а  "с не может быть меньше a". то есть   for (var c=a+1;c<100;c++) {
    Всего записей: 1891 | Зарегистр. 07-08-2002 | Отправлено: 21:39 31-12-2018 | Исправлено: Alex_Piggy, 22:00 31-12-2018
    r u b o a r d m a n



    BANNED    		Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
    Alex_Piggy
    Цитата:
    Если в данный момент времени известна формула u = (a*c)/(b*d) и известны: a,b,c и u
    Ошибочное утверждение - пожирнено
     
    Я попытался обрисовать задачу насколько можно доходчиво.
    Но видимо не теми словами.
     
    Итак. Постановка задачи (начну издалека чтобы доходчивее было):  
     
    1) Есть софт, написанный для ПК.
    Подробнее..
     
    2) Нужен аналогичный софт для Java 2ME MIDP 2.0 CLDC 1.1 (телефоны 40-й серии короче)
     
    3) Поскольку из-за специфики тормозов и убогости Java ME обычная реализация невозможна, надо найти алгоритм чтобы реализовать данный софт указанный в п.2.
     
    Вопрос. Реально ли найти такой алгоритм?  
     
    Всё. Вроде бы ничего не упустил. Всё же попробую проработать этот вариант.
    Всего записей: 484 | Зарегистр. 10-09-2014 | Отправлено: 22:24 31-12-2018 | Исправлено: r u b o a r d m a n, 22:54 31-12-2018
    Alex_Piggy

    Advanced Member    		Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
    r u b o a r d m a n

    Цитата:
    Цитата: Если в данный момент времени известна формула u = (a*c)/(b*d) и известны: a,b,c и u  Ошибочное утверждение - пожирнено

    "В данный момент времени" - это внутри третьего цикла перебора. a, c и b - определены.
     
    Ловите код на JScript. Смотрите, что я имел в виду. Сохранить как *.js , запустить. Выведет "лучший" результат, создаст возле себя result.txt с полным списком. Подробнее...
    PS: Можно начинать отсчет c с a, и проверять, что больше - d или b. Потому что если c < a - то эта комбинация уже была в виде a < c. С b и d то же самое.
    Всего записей: 1891 | Зарегистр. 07-08-2002 | Отправлено: 22:55 31-12-2018
    r u b o a r d m a n



    BANNED    		Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
    Alex_Piggy, ваш код, возможно правильно работает, но проверить на правильность немогу потому что a, b, c, d должны браться из определенного набора, как здесь.
     

    Цитата:
    Набор шестерен гитары:  
    20,20,23,24,25,25,30,33,34,35,37,40,41,43,45,47,48,50,53,55,57,58,59,60,61,62,65,67,70,71,73,75,79,80,83,85,89,90,92,95,97,98,100

     
    Примечание:
    Если не затруднит, листинги желательно на Делфи, в крайнем случае на VBScript, а впрочем как угодно.
    Я на Java листинг давал поскольку для телефона его готовил, а там сами понимаете только Java.
     
    Добавлено:

    Цитата:
    внутри третьего цикла перебора. a, c и b - определены.
    понятно. Неплохо придумано.  
    Все же перебрать 79 507 вариантов это не 3 418 801
    Всего записей: 484 | Зарегистр. 10-09-2014 | Отправлено: 23:11 31-12-2018 | Исправлено: r u b o a r d m a n, 23:26 31-12-2018
    Alex_Piggy

    Advanced Member    		Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
    r u b o a r d m a n

    Цитата:
    Если не затруднит, листинги желательно на Делфи, в крайнем случае на VBScript, а впрочем как угодно.


    Цитата:
    Набор шестерен гитары:  
     20,20,23,24,25,25,30,33,34,35,37,40,41,43,45,47,48,50,53,55,57,58,59,60,61,62,65,67,70,71,73,75,79,80,83,85,89,90,92,95,97,98,100

    Прошу прощения, не заметил. Изменил значения, выделенные жирным.
    На Delphi  я последний раз лет десять назад писал. Поэтому - увы - VBScript.
    aList - массив возможных шестерней, должен быть отсортирован по возрастанию.
     Подробнее...
    PS. С Новым Годом!
    Всего записей: 1891 | Зарегистр. 07-08-2002 | Отправлено: 01:51 01-01-2019
    r u b o a r d m a n



    BANNED    		Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
    Alex_Piggy и вас тоже с Новым Годом! Благодарю за помощь, буду тестировать и подгонять, надеюсь что все получится.
     
    По поводу массива перемноженных значений, то не всё так плохо. Накодил тут обновку - теперь варианты ( 2 * 3 ) и ( 3 * 2 ) считаются одинаковыми и один из вариантов отсекается как избыточный. Так же отсекаются варианты (3 * 3) с одинаковыми множителями - т.к. нельзя одну и ту же шестерню использовать два раза. вот что получилось:
    Листинг  
     
    При этом кол-во результатов сократилось с 1849 до 903, то есть почти половина - избыточные.
     
     
    Добавлено:
    Alex_Piggy
    Цитата:
    20,20,23,24,25,25,30,
    Это не ошибка. Они в наборе к этому станку так и идут, две пары одинаковые. У других станков повторяются другие пары. Из чего исходили проектировщики станков я не знаю.
     
     
    Добавлено:
    Что-то не то:

     
    У нас в наборе нет шестерни 26.
    Всего записей: 484 | Зарегистр. 10-09-2014 | Отправлено: 10:17 01-01-2019
    Alex_Piggy

    Advanced Member    		Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
    Доброе время, r u b o a r d m a n

    Цитата:
    нельзя одну и ту же шестерню использовать два раза ...
    Это не ошибка. Они в наборе к этому станку так и идут, две пары одинаковые.  

    Нельзя вообще? Или в одной связке (a-b),(c-d)? Или если нет повтора в списке? То есть для этого станка разрешены ли комбинации (a=20/b=25)*(с=20/d=30)  и  (a=55/b=25)*(с=55/d=30) ?
     

    Цитата:
    При этом кол-во результатов сократилось с 1849 до 903, то есть почти половина - избыточные.

    Вообще это называется комбинаторика. Но нам ее не преподавали. Сам немного разбирался...
    Это называется "Сочетания без повторений из n элементов по k".
    Считается n!/((n-k)! * k!) -  для k=2 формула упрощается до n * (n-1)/2. 43 элемента  A = n * (n-1) = 43*42/2 =  903 варианта (что Вы и получили). Без дубликатов - 41 элемент - A = 41 * 40 / 2 = 820  
    То что я встречал цикл перебора сочетаний без повторений - это и будет то, что предлагал
    for ia := Low(gears) to High(gears) do  for ib := ia+1 to High(gears) do  { loop}
    Только я считал, что c может быть таким же, как и a - поэтому использовал "c=a" (aka ib := ia ) а не "c=a+1".  

    Цитата:
    Листинг  

    Спасибо, этого достаточно. Cтавлю TurboPascal.
    Всего записей: 1891 | Зарегистр. 07-08-2002 | Отправлено: 11:33 01-01-2019
    r u b o a r d m a n



    BANNED    		Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
    Alex_Piggy
    Цитата:
    Нельзя вообще?
    Точно такую же можно. Именно эту нельзя. Как вы себе ЭТО представляете физически?
     

    Цитата:
    комбинаторика. Но нам ее не преподавали.
    На тоже. А жаль пригодилось бы.
     

    Цитата:
    Cтавлю TurboPascal.
    Да ладно вам.. Это Делфи.
     
    Обновил исходную процедуру, вроде бы и работает, и не работает - читайте комментарии в листинге. Что не так делаю?
    Процедура на Java
    Всего записей: 484 | Зарегистр. 10-09-2014 | Отправлено: 11:57 01-01-2019
    Alex_Piggy

    Advanced Member    		Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
    r u b o a r d m a n

    Цитата:
    У нас в наборе нет шестерни 26.

    Да. Я думал, что "25,25" - это опечатка и исправил на "25,26". И предупредил, что "Изменил значения, выделенные жирным.". Пожалуйста исправьте в коде обратно.
     

    Цитата:
    Точно такую же можно. Именно эту нельзя. Как вы себе ЭТО представляете физически?

    Точно. Протупил. Тогда циклы для ia ib ic будут так:
    from ia := Low(gears) to High (gears) do
    from ic := ia+1 to High (gears) do  
    from ib := Low(gears) to High (gears) do If  (ib <> ia)  And (ib <> ic) Then If (gears[ib] >= bmin) And (gears[ib] <= bmax) Then
     

    Цитата:
    Да ладно вам.. Это Делфи

    Pascal, Delphi - какая разница? В данном случае? В любом случае у меня ничего такого не стоит.
     

    Цитата:
    Процедура на Java

    То есть Вам таки на Java нужно.
    1. Вы отдельно крутите циклы, и отдельно строка, в которой вы ищете текстовые значения. Не надо так делать. Переведите строку в массив и работайте с индексами.  
    2. (ai*ci)/(bi*di) == u не будет работать. Почитайте, например, https://howtodoinjava.com/java/basics/correctly-compare-float-double/ . Вкратце - если будет отличатся двадцатый знак после запятой - то числа будут считаться разными. Поэтому лучше сравнивать с допуском - например
    Math.abs((ai*ci)/(bi*di) - u) < 0.00001
    Всего записей: 1891 | Зарегистр. 07-08-2002 | Отправлено: 12:32 01-01-2019
    r u b o a r d m a n



    BANNED    		Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
    Alex_Piggy
    Цитата:
    Math.abs
    На Java это будет работать. А на Java 2Me такой библиотеки не предусмотрено.  
    Так что придётся извращаться.
     
    Всего записей: 484 | Зарегистр. 10-09-2014 | Отправлено: 12:46 01-01-2019
    Открыть новую тему     Написать ответ в эту тему

    Страницы: 1 2 3 4 5 6 7 8 9 10 11

    Компьютерный форум Ru.Board » Компьютеры » Прикладное программирование » Алгоритмы


    Реклама на форуме Ru.Board.

    Powered by Ikonboard "v2.1.7b" © 2000 Ikonboard.com
    Modified by Ru.B0ard
    © Ru.B0ard 2000-2024

    BitCoin: 1NGG1chHtUvrtEqjeerQCKDMUi6S6CG4iC

    Рейтинг.ru