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

Новые блоги и статьи Все статьи Все блоги /
Расчёт периметра прямоугольника по координатам вершин Maks 18.07.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Вычислить периметр прямоугольника, заданного координатами своих вершин на плоскости. Решение: Создан документ со следующими. . .	Подсчёт частоты трёхбуквенных слов в тексте Maks 18.07.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Выясните, сколько раз в предложенном тексте встречается каждое трехбуквенное слово. Решение: Создан документ с единственным. . .	Сумма и количество положительных элементов в чётных строках массива Maks 18.07.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Вычислить сумму и количество положительных элементов массива, расположенных в четных строках. Решение: Создан документ с. . .	Поиск произведения положительных чётных чисел в последовательности Maks 18.07.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Дана произвольная последовательность целых чисел. Найти произведение положительных четных чисел данной последовательности. . . .
Обработка трёх чисел: утроение и возведение в степень Maks 18.07.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Даны три действительных числа. Утроить те из них, значения которых неотрицательны, и возвести в четвертую степень отрицательные. . . .	Расчёт стоимости яблок по весу Maks 18.07.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Написать программу вычисления стоимости некоторого количества (по весу) яблок. Решение: Создан документ, с табличной частью. . .	сукцессия 30. Фосфорный и азотный замки по "честному" закону лимитирования Либиха anaschu 16.07.2026 Основные достижения за последние дни 1. Механизм отложенного высвобождения фосфора Добавлен специальный пул для медленного разложения меланизированных гиф ЕСМ Реализована разная скорость. . .	Запрет пометки на удаление и отмены проведения Maks 16.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "ПутевойЛист" разработанного в КА2. Задача: запретить помечать на удаление и отменять проведения путевого листа при условии, если он сдан. . .

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

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