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

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Алг]Размещение арифметических операторов и скобок 
:(
    Опции темы
agl
Дата 20.3.2007, 17:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: 3
Всего: 3
Задача 6
б) Вводится строка не более чем из 6 цифр и некоторое целое число R. Расставить знаки арифметических операций ("+", "-", "*", "/"; минус не является унарным, т.е. не может обозначать отрицательность числа; деление есть деление нацело, т.е. 11/3=3) и открывающие и закрывающие круглые скобки так, чтобы получить в результате вычисления получившегося выражения число R. Лишние круглые скобки ошибкой не являются.

Например: Строка 505597, R=120: ((5+0)*((5*5)-(9/7)))=120.

Кто-то может объяснить, как сие чудо решить?
Моих мыслей практически нет, но всё же:
Перебираем все возможные комбинации арифметических операций и для каждой комбинации сделать перебор всех возможных комбинаций размещения скобок, ну и вычеслить результат. В общем для меня звучит ужасно.

Ещё интересный момент, при решении "подобной" задачи 6 пункт а: перебираем все возможные комбинации операторов и для каждой вычисляем результат. Вопрос: что делать, если встречаем деление на ноль? Я думаю надо считать подобную комбинацию не валидной. Это правильное решение?
PM   Вверх
Akina
Дата 20.3.2007, 19:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


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

Репутация: 17
Всего: 454
(50+5+5)*(9-7) - валидное решение?

А вообще... 

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

Следовательно, задача решаема простым перебором. Да, действительно ужасно. Но, как не крути, а варианты-то придется перебирать все. Не видать оптимизации что-то...

Цитата(agl @  20.3.2007,  18:42 Найти цитируемый пост)
Вопрос: что делать, если встречаем деление на ноль? Я думаю надо считать подобную комбинацию не валидной. Это правильное решение? 

А альтернатива? разрешить деление на ноль?


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.
PM MAIL WWW ICQ Jabber   Вверх
agl
Дата 20.3.2007, 23:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: 3
Всего: 3
Цитата
(50+5+5)*(9-7) - валидное решение?

Нет.

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

Следовательно, задача решаема простым перебором. Да, действительно ужасно. Но, как не крути, а варианты-то придется перебирать все. Не видать оптимизации что-то...

У меня и небыло сомнений насчёт решаемости задачи, проблема в нехватке знаний, чтобы написать действительно решение, а не велосипед.
Я знаю как написать код для расстановок знаков между группами, а с остальным проблема. Прошо помочь информацией(названием алгоритма, ссылкой на статью и т.д.) прочитав которую можно решить данную задачу, ну или готовым кодом, если у кого завалялся(тогда лучше на С).
Цитата(Akina)
Цитата(agl @  20.3.2007,  18:42 Найти цитируемый пост)
Вопрос: что делать, если встречаем деление на ноль? Я думаю надо считать подобную комбинацию не валидной. Это правильное решение? 

А альтернатива? разрешить деление на ноль?

Возможно кому то и смешно, но я просто советуюсь, т.к. больше не с кем, о правильности моего решения.


Это сообщение отредактировал(а) agl - 21.3.2007, 00:09
PM   Вверх
agl
Дата 21.3.2007, 09:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: 3
Всего: 3
Неужели никто подсказать не может, что нибудь почитать для решения данной задачи? Может кто знает, что из дескретки надо прочесть?
PM   Вверх
Бонифаций
Дата 21.3.2007, 16:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 1
Всего: 40
Цитата(Akina @  20.3.2007,  19:09 Найти цитируемый пост)
Количество вариантов расстановки скобок - конечно.


нет.

например 
(5+1)
 и
(((((((((((((((((((((((((((((((((((((((5+1)))))))))))))))))))))))))))))))))))))))))

и можно наращивать количество скобок бесконечно. Поэтому нельзя говорить что количество расстановок скобок конечно.

Добавлено @ 16:10 
Решение скажем при +-.* достаточно тривиальное решается рекурсией, проблему представляют только скобки.

Я бы предложил  сначала решать эту задачу с помошью польской  бесскобочной записи  (рекурсивно, перебором). А когда получите уже
5 0 +  5 5  * 9 7 / - *  уже преобразовывать это в обычную запись со скобками.



--------------------
 Бонифаций.
 
PM MAIL ICQ Skype GTalk Jabber YIM   Вверх
agl
Дата 21.3.2007, 16:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: 3
Всего: 3
Например, решение анологичной задачи, просто без заморочек со скобками. Вроде работает, по моим тестам, и без всякой рекурсии. Алгоритм взят с сайта algolist(ссылка в моем первом посте имеется).


Задача 6.

a) В написанном выражении ((((1?2)?3)?4)?5)?6 вместо каждого знака ? вставить знак одной из 4 арифметических операций +,-,*,/ так, чтобы результат вычислений равнялся 35 (при делении дробная часть в частном отбрасывается). Найти все решения.

Код

#include <stdio.h>
#define N 6

void print_arr(int *arr, int n)
{
    int i;
    for(i = 0; i < n; i++)
        printf("%3d", arr[i]);
    putchar('\n');
    putchar('\n');
}

int main(void)
{
    enum op {ADD, SUB, MUL, DIV}; // 0, 1, 2, 3
    int operators[N] = {0};// the elements array can be the digit from 0(ADD) to 3(DIV)
    int i, rez, j=1, k, R = 10;
    char arr_digits[N+1] = "505597";

    for(i = 0; i < N; i++)
    {
        while(!operators[N-1])
        {
            ///check total
            k = 0;
            rez = arr_digits[k++] - '0';
            while(arr_digits[k])
            {
                switch(operators[k-1])
                {
                    case ADD: rez += (arr_digits[k++] - '0'); break;
                    case SUB: rez -= (arr_digits[k++] - '0'); break;
                    case MUL: rez *= (arr_digits[k++] - '0'); break;
                    case DIV: if(arr_digits[k]-'0')rez /= (arr_digits[k++] - '0'); else k++; break;
                    default: printf("Default"); k++;
                }

            }
    
            if(rez == R){
                printf("%8s%2c%1d:\n", "Subset",'#',j);
                printf("Is Searched!!  Rez = %d\n", rez);
                print_arr(operators, N-1);
            }
            j++;
    
            i = 0;
            while(operators[i] == 3) operators[i++] = 0;
            operators[i]++;
        }
    }
    


    return 0;
}



Цитата
Я бы предложил  сначала решать эту задачу с помошью польской  бесскобочной записи  (рекурсивно, перебором). А когда получите уже
5 0 +  5 5  * 9 7 / - *  уже преобразовывать это в обычную запись со скобками.

Мне не совсем понятен ваш совет ((. Речь идет о цифрах и их организации при добавлении скобок и операторов, для нахождения всех комбинаций, которые в результате дадут заданное число Р.
В любом случае спасибо, вы первый отозвались и попытались помочь советом  smile 
Должен быть метод перебрать все возможные группировки данных цифр(насколько я пониманию получить все возможные группировки данных == размещению скобок), в общем путанница в голове :((

Это сообщение отредактировал(а) agl - 21.3.2007, 16:34
PM   Вверх
Бонифаций
Дата 21.3.2007, 16:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 1
Всего: 40
Цитата(agl @  21.3.2007,  16:32 Найти цитируемый пост)
и ((((1?2)?3)?4)?5)?6 


нет это немного не такая задача. тут позиции скобок  и операций фиксированы. Поэтому тут перебор очень простой.

Добавлено @ 16:44 
Цитата(agl @  21.3.2007,  16:32 Найти цитируемый пост)
Мне не совсем понятен ваш совет


попробую обьяснить. Есть тн "обратная польская запись" выражений (АКА стековая запись). Она часто используется например при геренации кода. Или например в языке форт. Или в постскрипте. Ее достоинство - не нужно никаких скобок. 

то есть 5 + 5 записывается как 5 5 +
(5+5) * (6-2)  будет  5 5 + 6 2 - *
и тд

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

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






--------------------
 Бонифаций.
 
PM MAIL ICQ Skype GTalk Jabber YIM   Вверх
agl
Дата 21.3.2007, 16:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: 3
Всего: 3
Правильно, не такая. Здесь линейное вычесление, т.е берем по порядку каждый элемент.
В задачи, которую я не могу решить, в принцепе проблема с расстоновкой скобок. Насколько я понимаю, берем текущий набор операторов(массив operators), и затем надо найти все возможные варианты размещения скобок и вычеслить с каждым вариантом расмещения скобок с текущим набором операторов. Вопрос как это сделать? Рекурсивно не рекурсивно - это второй вопрос, мне нужен толчёк - информация, которая поможет написать алгоритм. 

Вы считаете мне надо почитать инфу о "польской  бесскобочной записи"? Если нужно - почитаю, если в интернете нормальную инфу найду.

Добавлено @ 16:49 
Цитата
делается элементарно

Спасибо, подумаю над вашим советом.
PM   Вверх
Бонифаций
Дата 21.3.2007, 17:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 1
Всего: 40
вот вам для затравки:
Я сделал набросок на питоне чтобы продемострировать как работает такой алгоритм.
Вот резальтаты:

(5 * (0 + ((5 * 5) - (9 / 7))))
(5 * ((0 + (5 * 5)) - (9 / 7)))
(5 * (((0 + 5) * 5) - (9 / 7)))
((5 + 0) * ((5 * 5) - (9 / 7)))
((5 - 0) * ((5 * 5) - (9 / 7)))

Вот программа. Разбирайтесь
Код

#!/usr/bin/env python
from string import atoi
sq = ['5','0','5','5','9','7']
res = 120


def convert_to_normal(postfix):
    stack = []
    for node in postfix:
        if (node in ['*','/','+','-']):
            n1 = stack[-1]
            del(stack[-1])
            n2 = stack[-1]
            del stack[-1]
            stack.append("(%s %s %s)"%(n2,node,n1))
        else:
            stack.append(node)    
    return stack[-1]        

def evaluate_postfix(postfix):
    stack = []
    for node in postfix:
        if (node == '*'):
            n1 = stack[-1]
            del(stack[-1])
            n2 = stack[-1]
            del stack[-1]
            stack.append(n2 * n1)
        elif  (node == '+'):
            n1 = stack[-1]
            del(stack[-1])
            n2 = stack[-1]
            del stack[-1]
            stack.append(n2 + n1)
        elif  (node == '-'):
            n1 = stack[-1]
            del(stack[-1])
            n2 = stack[-1]
            del stack[-1]
            stack.append(n2 - n1)
        elif  (node == '/'):
            n1 = stack[-1]
            del(stack[-1])
            n2 = stack[-1]
            del stack[-1]
            if (n1 == 0):
                stack.append(0)
            else:       
                stack.append(n2 / n1)
        else:
            stack.append(atoi(node))
    return stack[-1]        

def workout(src, r,stacksize,  postfix):
    if ( stacksize == 1) and (len(src) == 0):
        if (evaluate_postfix(postfix) == r):
            print convert_to_normal(postfix)
        return
    if (len(src)>0):
       head = src[0]
       tail = src[1:]
       workout(tail,r,stacksize+1,postfix+[head])
    if (stacksize >= 2):
       workout(src,r,stacksize-1,postfix+['*'])   
       workout(src,r,stacksize-1,postfix+['/'])   
       workout(src,r,stacksize-1,postfix+['+'])   
       workout(src,r,stacksize-1,postfix+['-'])   
    
    


workout(sq,120,0,[])    



здесь есть одна небрежность - деление на 0 у меня дает 0 (это просто лень обрабатывать эту ситуацию) так что будьте внимательнее когда будете разбираться

Это сообщение отредактировал(а) Бонифаций - 21.3.2007, 17:51


--------------------
 Бонифаций.
 
PM MAIL ICQ Skype GTalk Jabber YIM   Вверх
agl
Дата 22.3.2007, 15:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: 3
Всего: 3
Бонифаций, спасибо БОЛЬШОЕ, попробую разобраться
PM   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

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


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

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

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

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


 




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


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

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