Получить заданное число 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 будет считать ненамного дольше. Уже написал первую часть алгоритма, вторая нужна только в отдельных случаях.
ЗЫ не могу из консоли скопировать сюда результаты работы, надо в файл писать - разбираться как. Но в консоли все отлично показывает

Новые блоги и статьи Все статьи Все блоги /
Nekobox - outbounds[0].transport: unknown transport type: raw damix 01.10.2026 Фикс ошибки Правым кликом по серверу -> отладочная информация -> edit Заменить "net": "raw", на "net": "tcp", Нажать кнопку reload.	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .

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

	Получить заданное число m сложением/вычитанием цифр 22.09.2014, 17:31. Показов 5688. Ответов 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