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

Новые блоги и статьи Все статьи Все блоги /
FSharp: interface of module DevAlt 16.05.2026 Интерфейс модуля F# позволяет управлять доступностью членов, содержащихся в реализации модуля. По-умолчанию все члены модуля доступны: module Foo let x = 10 let boo () = printfn "boo" . . .	Хитросплетение родственных связей пантеона греческих богов. russiannick 14.05.2026 Однооконник, позволяющий узреть и изучить отдельных героев древней Греции. <!DOCTYPE html> <html lang="ru"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible". . .	[golang] Угол между стрелками часов alhaos 12.05.2026 По заданным значениям часа и минуты необходимо определить значение меньшего угла между стрелками аналогового циферблата часов. import "math" func angleClock(hour int, minutes int) float64 { . . .	Debian 13: Установка Lazarus QT5 ВитГо 09.05.2026 Эта инструкция моя компиляция инструкций volvo https:/ / www. cyberforum. ru/ blogs/ 203668/ 10753. html и его же старой инструкции по установке Lazarus с gtk2. . .
Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .	Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .	попытка написать игровой сервер на C++ pyirrlicht 29.04.2026 попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .	Контроль уникальности выбранного документа-основания при изменении реквизита Maks 28.04.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .

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

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