Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Олександr
0 / 0 / 0
Регистрация: 15.12.2013
Сообщений: 10
#1

Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность - C++

01.03.2014, 21:27. Просмотров 1316. Ответов 20
Метки нет (Все метки)

Программа должна перемножать 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность(помогите написать хотя бы рекурсивную функцию я то я вообще не могу вьехать))
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.03.2014, 21:27
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность (C++):

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

Не используя никаких операций, кроме умножения и присваивания, составить программу, вычисляющую a7 за 4 операции умножения
1.Дано число a. Не используя никаких операций, кроме умножения и присваивания,...

Определить значение n^3, не используя операции умножения
Определить значение {n}^{3}, не используя операции умножения. Известно что:...

Используя do while перемножить вводимые числа
Направьте в нужную сторону. Задача: пользователь вводит много чисел, которые...

Написать программу умножения ряда нечётных натуральных чисел от 1 до 21, используя указатели
Добрый день! Есть задача, умножить числа 1 * 3 * 5 * 7 * ...* 21, используя...

Возвести число в 10 степень, используя только четыре операции умножения
Подскажите что не так?При проверке на сайте пишет частичное решение. Задача:...

20
Рыжий Лис
Просто Лис
913 / 451 / 322
Регистрация: 17.05.2012
Сообщений: 1,857
Записей в блоге: 7
01.03.2014, 21:54 #2
Кликните здесь для просмотра всего текста
Bash
1
2
3
4
5
6
7
8
9
10
11
12
13
scala> def f(n:Int,m:Int):Int={
     | if(m==0) 0
     | else n+f(n,m-1)
     | }
f: (n: Int, m: Int)Int
 
scala> f(2,2)
res1: Int = 4
 
scala> f(2,3)
res2: Int = 6
 
scala>


C++
1
2
3
4
int f(int n, int m){
  if (m==0) return 0;
  else return n+f(n,m-1);
}
1
DrOffset
7518 / 4514 / 1097
Регистрация: 30.01.2014
Сообщений: 7,362
01.03.2014, 23:17 #3
Цитата Сообщение от Рыжий Лис Посмотреть сообщение
C++
1
2
3
4
int f(int n, int m){
    if (m==0) return 0;
    else return n+f(n,m-1);
}
такая функция будет дольше исполняться, если второй аргумент больше первого, и чем больше между ними разница, тем заметнее будет замедление.
Поэтому можно предложить такую оптимизацию:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
unsigned int multiply1(unsigned int a, unsigned int b)
{
    return b == 0 ? 0 : multiply1(a, b - 1) + a;
}
 
unsigned int multiply2(unsigned int a, unsigned int b)
{
    return a == 0 ? 0 : multiply2(a - 1, b) + b;
}
 
unsigned int mul(unsigned int a, unsigned int b)
{
    if(a == 0 || b == 0)
    {
        return 0;
    }
    return a > b ? (multiply1(a, b - 1) + a) : (multiply2(a - 1, b) + b);
}
2
Олександr
0 / 0 / 0
Регистрация: 15.12.2013
Сообщений: 10
02.03.2014, 18:04  [ТС] #4
не компилируется
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
27
28
29
30
31
32
33
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <math.h>
 
using namespace std;
 
unsigned int multiply1(unsigned int a, unsigned int b)
{
    return b == 0 ? 0 : multiply1(a, b - 1) + a;
}
unsigned int multiply2(unsigned int a, unsigned int b)
{
    return a == 0 ? 0 : multiply2(a - 1, b) + b;
}
unsigned int mul(unsigned int a, unsigned int b)
{
    if (a == 0 || b == 0)
    {
        return 0;
    }
    return a > b ? (multiply1(a, b - 1) + a) : (multiply2(a - 1, b) + b);
}
int _tmain(int argc, _TCHAR* argv[])
{
    int n1, n2;
    cout << "Enter n1,n2: ";
    cin >> n1;
    cin>>n2;
    cout << "n1*n2=" <<  mul(n1, n2) << endl; // вызов рекурсивной функции
    _getch();
    return 0;
}
что значит у visual studio "возникли ошибки сборки" ,я уже несколько программ не могу проверить из-за этих ошибок сборки..хотя все вроде правильно.
0
DrOffset
7518 / 4514 / 1097
Регистрация: 30.01.2014
Сообщений: 7,362
02.03.2014, 18:38 #5
Может сами ошибки-то покажешь?
0
zer0mail
2451 / 2085 / 216
Регистрация: 03.07.2012
Сообщений: 7,566
Записей в блоге: 1
02.03.2014, 18:42 #6
Решения "в лоб" не дадут логарифмической сложности. Интересно, операции разрядного сдвига вправо/влево допустимы?
0
Олександr
0 / 0 / 0
Регистрация: 15.12.2013
Сообщений: 10
02.03.2014, 23:39  [ТС] #7
DrOffset, вот такое постоянно выбрасывает ..теряюсь в догадках потому что никаких ошибок не вижу..и это происходит последним временем по отношении ко всем программам которые пишу.
0
Миниатюры
Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность  
DrOffset
7518 / 4514 / 1097
Регистрация: 30.01.2014
Сообщений: 7,362
02.03.2014, 23:43 #8
Цитата Сообщение от Олександr Посмотреть сообщение
вот такое постоянно выбрасывает
А внизу в логе ошибок что пишет?
0
Олександr
0 / 0 / 0
Регистрация: 15.12.2013
Сообщений: 10
02.03.2014, 23:44  [ТС] #9
zer0mail, я относительно недавно пишу в среде так что я даже не знаю что вы у меня спросили.Задание полностью изложено.Возможен вариант программы без логарифмической сложности.
0
Олександr
0 / 0 / 0
Регистрация: 15.12.2013
Сообщений: 10
02.03.2014, 23:48  [ТС] #10
DrOffset,ничего по сути.Ошибки не подчеркивает.
0
Миниатюры
Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность  
Олександr
0 / 0 / 0
Регистрация: 15.12.2013
Сообщений: 10
02.03.2014, 23:49  [ТС] #11
DrOffset, я уже думаю что у меня что то с вижуалом.
0
DrOffset
7518 / 4514 / 1097
Регистрация: 30.01.2014
Сообщений: 7,362
03.03.2014, 00:15 #12
Олександr, архивируй проект целиком, можешь кинуть мне в личку или сюда, я посмотрю. Возможно что-то с настройками проекта.
0
UnsKneD
алкокодер
155 / 151 / 41
Регистрация: 27.12.2012
Сообщений: 550
03.03.2014, 00:19 #13
Олександr, а если просто хуллоу ворлд вывести?
0
Олександr
0 / 0 / 0
Регистрация: 15.12.2013
Сообщений: 10
04.03.2014, 22:14  [ТС] #14
Архив с програмой
0
Вложения
Тип файла: rar Лаб 1.3.rar (1.96 Мб, 4 просмотров)
Олександr
0 / 0 / 0
Регистрация: 15.12.2013
Сообщений: 10
04.03.2014, 22:20  [ТС] #15
UnsKneD,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include "stdafx.h"
 
#include <iostream>
#include <conio.h>
#include <math.h>
 
 
using namespace std;
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    cout << "Hello,world";
    return 0;
}
НЕ КАТИТ(возникли ошибки сборки)
0
DrOffset
7518 / 4514 / 1097
Регистрация: 30.01.2014
Сообщений: 7,362
04.03.2014, 23:31 #16
Олександr, скачал твой проект, запустил - работает все нормально.
Версия Visual Studio какая? Может попробовать ее переустановить?
0
ValeryS
Модератор
7134 / 5402 / 669
Регистрация: 14.02.2011
Сообщений: 18,227
05.03.2014, 00:03 #17
Цитата Сообщение от zer0mail Посмотреть сообщение
Решения "в лоб" не дадут логарифмической сложности. Интересно, операции разрядного сдвига вправо/влево допустимы?
а если нет?
то можно использовать умножение на 2
вот в таком виде
C++
1
a+=a;
но вот деление не знаю как

а так можно поразрядно умножать (разряды двоичные)

примерно так
C++
1
2
3
4
5
6
7
8
9
10
int fncMul(int a, int b,)
{
 if(b==0)
  return 0;
 if(b&1)
  return a+fncMul(a+a,b/2); 
 else
  return fncMul(a+a,b/2);
 
}
Добавлено через 50 секунд
Цитата Сообщение от Олександr Посмотреть сообщение
НЕ КАТИТ(возникли ошибки сборки)
может покажешь какие?
1
UnsKneD
алкокодер
155 / 151 / 41
Регистрация: 27.12.2012
Сообщений: 550
05.03.2014, 04:48 #18
Цитата Сообщение от Олександr Посмотреть сообщение
НЕ КАТИТ(возникли ошибки сборки)
студию не обновляли? другую студию поверх этой не ставили?
1
zer0mail
2451 / 2085 / 216
Регистрация: 03.07.2012
Сообщений: 7,566
Записей в блоге: 1
05.03.2014, 14:04 #19
Цитата Сообщение от ValeryS Посмотреть сообщение
Сообщение от zer0mail
Решения "в лоб" не дадут логарифмической сложности. Интересно, операции разрядного сдвига вправо/влево допустимы?
а если нет?
то можно использовать умножение на 2
Если нет, то придется складывать и "складывать сложенное" При аккуратной работе можно обойтись и без деления. Но неясно, какой уровень подготовки предполагает это задание.
0
ValeryS
Модератор
7134 / 5402 / 669
Регистрация: 14.02.2011
Сообщений: 18,227
05.03.2014, 14:17 #20
Цитата Сообщение от zer0mail Посмотреть сообщение
При аккуратной работе можно обойтись и без деления.
как?
вот с делением я показал как реализовать лог. зависимость
Цитата Сообщение от zer0mail Посмотреть сообщение
то придется складывать и "складывать сложенное"
не понял переведи
1
05.03.2014, 14:17
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.03.2014, 14:17
Привет! Вот еще темы с решениями:

Используя рекурсию вивести групу даних с их индексами не используя масив
Вот мой код на с++ #include&lt;iostream&gt; #include&lt;conio.h&gt; using namespace std;...

Не используя операции умножения и деления, найти количество отрезков, расположенных на отрезке А
Прошу еще раз, прочитайте правила форума:...

Цикл: Используя только операции умножения и деления вычислить: A^n (A в степени n) , минимизировав число операций
Дано натуральное число A ( Ввод числа производится в шеснадцатеричной системе...

найти индекс по по значению числа, используя рекурсию.
Здравствуйте! Есть инициализированный и отсортированный массив определенного...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru