Получить заданное число m сложением/вычитанием цифр

@Roshki · Регистрация: 17.09.2014

Студворк — интернет-сервис помощи студентам

Очень-очень нужна помощь!
дано n (n>=2) количество цифр от 1 до 9 и любое число m. Написать программу расстановки между каждой парой чисел, записанных именно в таком порядке, знаков "+" и "-" так, чтобы значение полученного выражения равнялось m.

@_Ivana · 23.09.2014, 01:06

У меня тупое переборное. Причем, сырое - буду еще код ужимать. Да, у меня "типично сишный подход"

Зато весь код влезает на экран без полосы прокрутки и имхо все очень наглядно и понятно.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include "stdafx.h"
#include <iostream>
using namespace std; 
 
void find(int *pd, int n, int m, int s, char *pr, char *pr0)
{
    if (n == 0) {
        if (s == m) {*pr = 0; cout<<" "<<pr0<<" = "<<s<<endl;}
        return;
    }
    *pr = '+'; find(pd+1, n-1, m, s+*pd, pr+1, pr0);
    *pr = '-'; find(pd+1, n-1, m, s-*pd, pr+1, pr0);
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    int d[] = {1, 4, 2, 2}, m = 5;
    const int n = sizeof(d)/sizeof(int);
    char r[n];
 
    for(int i=0; i<n; i++) cout<<d[i]; cout<<endl;
    find(d+1, n-1, m, d[0], r, r);
 
    system("pause");
    return 0;
}

@Mr.X · 23.09.2014, 01:34

Сообщение от _Ivana

Зато весь код влезает на экран

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

Сообщение от _Ivana

имхо все очень наглядно и понятно.

М-да, насчет наглядности рекурсивной функции с шестью аргументами, да еще которые вместо слов буковками обозначены, утверждение, мягко говоря, спорное. Наглядность программы на С++ в том и состоит, что там используются стандартные, т.е. общеизвестные алгоритмы, а в вашем самопальном сишном, зашифрованном буковками нужно разбираться. К тому же правильность работы стандартных алгоритмов гарантирована, а самопальных - требует доказательства.
Кстати, мне вот всегда было интересно, а в чем сакральный смысл использования в именах буковок вместо слов?

@_Ivana · 23.09.2014, 01:42

Ну эта тема холиварная. Когда я пишу на 1С, я наоборот имена переменным длиннющие даю, ЧтобыПотомМожноБылоСразуПонятьЧтоОнаОбоз начает

А на Си тоже есть свои традиции: i:локальный счетчик цикла, p... - указатель на что-либо, и т.д.
ЗЫ я и случайную генерацию в три строки наглядно в код вставлю, не в этом дело. И я конечно не знаю С++, но не думаю что паттерны разработки прямо так жестко заставляют пользоваться только "стандартными отлаженными алгоритмами".

ЗЗЫ да что спорить - давайте устроим голосовалку в отдельной теме, кому больше понятен и близок мой код, а кому ваш - и посмотрим результаты

Я только не знаю как тут голосовалку делать.

@Mr.X · 23.09.2014, 01:45

Ну и, мне кажется, генерацию данных и печать следует все-таки разделять. Да и печатает ваша программа не арифметические выражения, а другое что-то.
В общем, экономия строк и буковок у вас идея-фикс, в угоду которой вы готовы всем пожертвовать.

@S_el · 23.09.2014, 01:46

Не по теме:

И сделаем вариант: непонятны обе реализации. :)

_Ivana, переменные надо называть так,чтобы другой человек(или вы,через определенное время) не терял ценное время на понимание зачем та или иная переменная предназначена.

Ваш вариант выглядит изящнее,но разобраться в нем не зная исходной задачи будет не просто.

@_Ivana · 23.09.2014, 01:48

Ага, еще и Haskell сейчас пытаюсь изучать - там ваще принято экономить строчки и буковки

Я же не говорю про ваши идеи-фикс. Давайте сделаем голосовалку - повторяю. Кто знающий традиции форума - подскажите, как это здесь лучше организовать?

@S_el · 23.09.2014, 01:50

Не по теме:

Сообщение от _Ivana

Ага, еще и Haskell сейчас пытаюсь изучать - там ваще принято экономить строчки и буковки

Переносить традиции Hаskell на C++ спорная идея.Вот если бы наоборот :)

@_Ivana · 23.09.2014, 01:50

Сообщение от S_el

но разобраться в нем не зная исходной задачи будет не просто

Не, ну вот это конечно аргумент!

При чтении кода хорошо бы знать исходную задачу, для которой он создавался. А восстанавливать "замысел творца" по тексту кода я сам постоянно вынужден конечно по работе, но все-таки.... Можно комментариев написать море, но я же спешил выложить свой код, не до них было.

@SlavaSSU · 23.09.2014, 01:52

_Ivana, а голосование будет не объективно. Просто все новички проголосуют за твой код, т.к. у МрИКСа он будет для них непонятный и громоздкий с кучей неизвестных слов. Кого-то на работе приучили так называть переменные и он проголосует за МрИКСа. Кого-то в универе научили по-другому. Вот давайте потягаемся в скорости работы))) К примеру при n == 50 m = rand() % 500? для начала)?

@Mr.X · 23.09.2014, 01:52

Сообщение от S_el

И сделаем вариант: непонятны обе реализации.

В моей-то чего непонятного? Для того, кто знает алгоритмы STL, там все очевидно, по-моему.

@КОП · 23.09.2014, 01:53

Сообщение от _Ivana

i:локальный счетчик цикла, p... - указатель на что-либо, и т.д.

а потом буковки кончаются и ступор...
int s - по логике это тогда должна быть строка

Не по теме:

а вообще что вы ясностью и строчками меряетесь, всем давно известно, у кого символов в коде меньше, тот и прав :D пруф

@S_el · 23.09.2014, 01:53

Сообщение от _Ivana

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

У меня,конечно,такого опыта работы нет,но вы сами подтверждаете мои слова

Сообщение от _Ivana

Можно комментариев написать море, но я же спешил выложить свой код, не до них было.

Я где-то читал,что если комментов больше,чем кода,то либо кривой код,либо комментарии.

@_Ivana · 23.09.2014, 01:56

Сообщение от SlavaSSU

Вот давайте потягаемся в скорости работы)))

Так нечестно

Вот с МрИКСом я бы в скорости потягался

А вы заявляете, что у вас не полный перебор, там сложность алгоритма асимптотически принципиально другая, чего же с вами тягаться

По крайней мере, не этим моим алгоритмом.

Добавлено через 1 минуту
ЗЫ и насчет объективности голосования - она и не нужна. Мы же не объективное решение выносим, а просто выбор и предпочтения множества субъективных имхообладателей.

@S_el · 23.09.2014, 02:00

Сообщение от КОП

а потом буковки кончаются и ступор...

Когда буковки кончаются начинаем добавлять _ справа и слева от имени.

Сообщение от _Ivana

А вы заявляете, что у вас не полный перебор, там сложность алгоритма асимптотически принципиально другая, чего же с вами тягаться

Значит и тягаться не стоит.

Сообщение от Mr.X

В моей-то чего непонятного? Для того, кто знает алгоритмы STL, там все очевидно, по-моему.

Уверен,что разобраться будет не сложно,но прочитав условие задачи и сопоставив с длинной кода подумал,что задачу понял не верно.
А SlavaSSU, правильно сказал:

Просто все новички проголосуют за твой код, т.к. у МрИКСа он будет для них непонятный и громоздкий с кучей неизвестных слов.

Т.е для того,чтобы вникнуть в вариант _Ivana нужно будет посидеть с бумажкой,разбирать алгоритм,а в вашем придется узнавать новое по всем функциям из подключаемых заголовков.

@Mr.X · 23.09.2014, 02:01

Сообщение от _Ivana

Можно комментариев написать море

А можно сделать код самодокументируемым, что специалисты и советуют делать.

@_Ivana · 23.09.2014, 02:04

У меня он и так самодокументируемый - s накопительная сумма, d - массив дигитов (разрядов, цифр), r - результат, pd|pr - указатели на соответствующие массивы, pr0 - указатель на начало массива результата, m - терминология ТС, i - локальный счетчик, n - количество итераций. Что непонятного-то? Файнд - найти, да (по аглицки).

@Mr.X · 23.09.2014, 02:06

Сообщение от _Ivana

У меня он и так самодокументируемый - s накопительная сумма, d - массив дигитов (разрядов, цифр), r - результат, pd|pr - указатели на соответствующие массивы, pr0 - указатель на начало массива результата, m - терминология ТС, i - локальный счетчик, n - количество итераций. Что непонятного-то? Файнд - найти, да (по аглицки).

Ну, он был бы таковым, если бы вы все это в именах и написали.

@_Ivana · 23.09.2014, 14:57

Ладно, оставим пустой спор. Я пишу так, вы - эдак, хорошо, что в мире такое разнообразие

А вот насчет в скорости посоревноваться - это более интересная идея

Пока не готов (со Славой, с МрИКСом то всегда готов - посмотрим, чем платят за обилие библиотечных методов), но кто знает

Добавлено через 12 часов 45 минут

Сообщение от SlavaSSU

Вот давайте потягаемся в скорости работы))) К примеру при n == 50 m = rand() % 500? для начала)?

Вот я немножко подумал и теперь готов с вами потягаться в скорости

Правда, я пока не реализовал свой алгоритм в коде.
Давайте уточним условия - исходные числа от 1 до 9 включительно, надо найти только один единственный вариант расстановки знаков или принять решение, что такового нет. Если да, то ставлю на то, что мой пока не написанный код будет работать доли секунды для n == 1 000 000 000 и любого m. Причем, будет всего несколько строчек кода.
ЗЫ и, кстати, думаю, его можно будет доработать для выдачи всех вариантов расстановки, а не только одного, но тогда он будет побольше, чем несколько строчек.
Если вам интересно - давайте посоревнуемся, буду реализовывать алгоритм в коде.

@SlavaSSU · 23.09.2014, 16:05

_Ivana, для n == 10^9? o.O WTF? че там за алгоритм ты придумал? математику какую-то? не ну миллиард это слишком. давай для 100 цифр. а то миллиард чисел и не проверишь на верность. А еще верно ли, что твой алгоритм не работает, если даны не цифры, а числа ну скажем до 1000?

@_Ivana · 23.09.2014, 16:11

SlavaSSU, хорошо, давай для 100 цифр, хотя, повторюсь, у меня и для 10^9 будет считать ненамного дольше. Уже написал первую часть алгоритма, вторая нужна только в отдельных случаях.
ЗЫ не могу из консоли скопировать сюда результаты работы, надо в файл писать - разбираться как. Но в консоли все отлично показывает

Новые блоги и статьи Все статьи Все блоги /
сукцессия 29. Переход от одних деревьев на другие делать более или менее вероятностным? anaschu 12.07.2026 Насколько смена типов микоризы — исключительное событие в двухвековой сукцессии? Оценка вероятности в пространстве параметров В текущей версии модели успешно реализован ключевой механизм. . .	сукцессия 27. Думаю, как переделывать уже написанную статью с планами на сукцессию. anaschu 12.07.2026 Анализ соответствия модели требованиям Реализованные компоненты: Механизм закисления почвы через протонную помпу Конкуренция между типами микориз pH как триггер сукцессии C/ P соотношение. . .	Сукцессия 26. Мат модель создана. anaschu 12.07.2026 Модель смены растительных сукцессий посредством управления грибами работает внутри небольшой ячейки почвы, восстанавливающейся после пожара, где ненадолго бывшее царство хвойных снова захватили. . .	Решил проблему с ошибкой пагинации сообщений с сервера на алгоритме обхода дерева "Эстафета хвоста". Hrethgir 12.07.2026 Проблема была в том, что удалялась именно новая кнопка, а не старая. Ни один ИИ не обнаружил это, а сам я смог только когда с работой стало попроще и когда заставил работать будущее автономное. . .
сукцессия 25. Хронология ошибок anaschu 12.07.2026 # От 50-тонного гриба до устойчивого леса: хроника ошибок при построении модели вековой сукцессии микоризы ## О чём эта статья В процессе построения ОДУ-модели (система дифференциальных. . .	сукцессия 24. Промежуточное общее описание модели anaschu 12.07.2026 Хендофф: модель АМ→ЭКМ сукцессии микоризы (ризосфера, 50 лет) Содержание проекта Симуляция вековой (50 лет) экологической сукцессии в почве леса Основные участники: АМ-гриб, ЭКМ-гриб,. . .	сукцессия 23. Более физиологичная физиология, более экологичная экология, более диффурные диффуры. anaschu 12.07.2026 Что реально нашли и починили за эти 5 часов Правило Линдемана (КПД конверсии сахара в тело, kEff) — раньше 100% полученного углерода шло прямо в биомассу гриба; теперь только kEff=0. 5 (после. . .	сукцессия 22. От артефактов к физиологии: калибровка агентной модели грибной сукцессии для воспроизведения сезонной динамики и pH-плато anaschu 11.07.2026 Аннотация В данной работе представлена калибровка агентной модели динамики грибных сообществ (fungal-succession), направленная на устранение нефизичных артефактов (коллапс биомассы, мгновенное. . .

@Roshki 0 / 0 / 0 Регистрация: 17.09.2014 Сообщений: 9

	Получить заданное число m сложением/вычитанием цифр 22.09.2014, 17:31. Показов 5456. Ответов 81 Метки нет (Все метки) Очень-очень нужна помощь! дано n (n>=2) количество цифр от 1 до 9 и любое число m. Написать программу расстановки между каждой парой чисел, записанных именно в таком порядке, знаков "+" и "-" так, чтобы значение полученного выражения равнялось m. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	23.09.2014, 01:42
	Ну эта тема холиварная. Когда я пишу на 1С, я наоборот имена переменным длиннющие даю, ЧтобыПотомМожноБылоСразуПонятьЧтоОнаОбоз начает А на Си тоже есть свои традиции: i:локальный счетчик цикла, p... - указатель на что-либо, и т.д. ЗЫ я и случайную генерацию в три строки наглядно в код вставлю, не в этом дело. И я конечно не знаю С++, но не думаю что паттерны разработки прямо так жестко заставляют пользоваться только "стандартными отлаженными алгоритмами". ЗЗЫ да что спорить - давайте устроим голосовалку в отдельной теме, кому больше понятен и близок мой код, а кому ваш - и посмотрим результаты Я только не знаю как тут голосовалку делать. 0

@Mr.X 3225 / 1752 / 436 Регистрация: 03.05.2010 Сообщений: 3,867
	23.09.2014, 01:45
	Ну и, мне кажется, генерацию данных и печать следует все-таки разделять. Да и печатает ваша программа не арифметические выражения, а другое что-то. В общем, экономия строк и буковок у вас идея-фикс, в угоду которой вы готовы всем пожертвовать. 0

@S_el 2444 / 1842 / 406 Регистрация: 15.12.2013 Сообщений: 8,243
	23.09.2014, 01:46
	Не по теме: И сделаем вариант: непонятны обе реализации. :) _Ivana, переменные надо называть так,чтобы другой человек(или вы,через определенное время) не терял ценное время на понимание зачем та или иная переменная предназначена. Ваш вариант выглядит изящнее,но разобраться в нем не зная исходной задачи будет не просто. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	23.09.2014, 01:48
	Ага, еще и Haskell сейчас пытаюсь изучать - там ваще принято экономить строчки и буковки Я же не говорю про ваши идеи-фикс. Давайте сделаем голосовалку - повторяю. Кто знающий традиции форума - подскажите, как это здесь лучше организовать? 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	23.09.2014, 01:52
	_Ivana, а голосование будет не объективно. Просто все новички проголосуют за твой код, т.к. у МрИКСа он будет для них непонятный и громоздкий с кучей неизвестных слов. Кого-то на работе приучили так называть переменные и он проголосует за МрИКСа. Кого-то в универе научили по-другому. Вот давайте потягаемся в скорости работы))) К примеру при n == 50 m = rand() % 500? для начала)? 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	23.09.2014, 02:04
	У меня он и так самодокументируемый - s накопительная сумма, d - массив дигитов (разрядов, цифр), r - результат, pd\|pr - указатели на соответствующие массивы, pr0 - указатель на начало массива результата, m - терминология ТС, i - локальный счетчик, n - количество итераций. Что непонятного-то? Файнд - найти, да (по аглицки). 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	23.09.2014, 16:05
	_Ivana, для n == 10^9? o.O WTF? че там за алгоритм ты придумал? математику какую-то? не ну миллиард это слишком. давай для 100 цифр. а то миллиард чисел и не проверишь на верность. А еще верно ли, что твой алгоритм не работает, если даны не цифры, а числа ну скажем до 1000? 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	23.09.2014, 16:11
	SlavaSSU, хорошо, давай для 100 цифр, хотя, повторюсь, у меня и для 10^9 будет считать ненамного дольше. Уже написал первую часть алгоритма, вторая нужна только в отдельных случаях. ЗЫ не могу из консоли скопировать сюда результаты работы, надо в файл писать - разбираться как. Но в консоли все отлично показывает 0