Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Олександr
0 / 0 / 0
Регистрация: 15.12.2013
Сообщений: 10
01.03.2014, 21:27     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #1
Программа должна перемножать 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность(помогите написать хотя бы рекурсивную функцию я то я вообще не могу вьехать))
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.03.2014, 21:27     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность
Посмотрите здесь:

найти индекс по по значению числа, используя рекурсию. C++
C++ Не используя никаких операций, кроме умножения и присваивания, составить программу, вычисляющую a7 за 4 операции умножения
C++ Цикл: Используя только операции умножения и деления вычислить: A^n (A в степени n) , минимизировав число операций
C++ Используя рекурсию вивести групу даних с их индексами не используя масив
Написать функцию умножения двух,заданных с клавиатуры чисел, используя только операцию умножения и рекурсию C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Рыжий Лис
Просто Лис
 Аватар для Рыжий Лис
209 / 164 / 44
Регистрация: 17.05.2012
Сообщений: 611
Записей в блоге: 4
01.03.2014, 21:54     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #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);
}
DrOffset
6460 / 3834 / 885
Регистрация: 30.01.2014
Сообщений: 6,629
01.03.2014, 23:17     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #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);
}
Олександr
0 / 0 / 0
Регистрация: 15.12.2013
Сообщений: 10
02.03.2014, 18:04  [ТС]     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #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 "возникли ошибки сборки" ,я уже несколько программ не могу проверить из-за этих ошибок сборки..хотя все вроде правильно.
DrOffset
6460 / 3834 / 885
Регистрация: 30.01.2014
Сообщений: 6,629
02.03.2014, 18:38     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #5
Может сами ошибки-то покажешь?
zer0mail
2188 / 1871 / 187
Регистрация: 03.07.2012
Сообщений: 6,661
Записей в блоге: 1
02.03.2014, 18:42     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #6
Решения "в лоб" не дадут логарифмической сложности. Интересно, операции разрядного сдвига вправо/влево допустимы?
Олександr
0 / 0 / 0
Регистрация: 15.12.2013
Сообщений: 10
02.03.2014, 23:39  [ТС]     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #7
DrOffset, вот такое постоянно выбрасывает ..теряюсь в догадках потому что никаких ошибок не вижу..и это происходит последним временем по отношении ко всем программам которые пишу.
Миниатюры
Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность  
DrOffset
6460 / 3834 / 885
Регистрация: 30.01.2014
Сообщений: 6,629
02.03.2014, 23:43     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #8
Цитата Сообщение от Олександr Посмотреть сообщение
вот такое постоянно выбрасывает
А внизу в логе ошибок что пишет?
Олександr
0 / 0 / 0
Регистрация: 15.12.2013
Сообщений: 10
02.03.2014, 23:44  [ТС]     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #9
zer0mail, я относительно недавно пишу в среде так что я даже не знаю что вы у меня спросили.Задание полностью изложено.Возможен вариант программы без логарифмической сложности.
Олександr
0 / 0 / 0
Регистрация: 15.12.2013
Сообщений: 10
02.03.2014, 23:48  [ТС]     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #10
DrOffset,ничего по сути.Ошибки не подчеркивает.
Миниатюры
Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность  
Олександr
0 / 0 / 0
Регистрация: 15.12.2013
Сообщений: 10
02.03.2014, 23:49  [ТС]     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #11
DrOffset, я уже думаю что у меня что то с вижуалом.
DrOffset
6460 / 3834 / 885
Регистрация: 30.01.2014
Сообщений: 6,629
03.03.2014, 00:15     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #12
Олександr, архивируй проект целиком, можешь кинуть мне в личку или сюда, я посмотрю. Возможно что-то с настройками проекта.
UnsKneD
алкокодер
 Аватар для UnsKneD
153 / 149 / 11
Регистрация: 27.12.2012
Сообщений: 548
03.03.2014, 00:19     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #13
Олександr, а если просто хуллоу ворлд вывести?
Олександr
0 / 0 / 0
Регистрация: 15.12.2013
Сообщений: 10
04.03.2014, 22:14  [ТС]     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #14
Архив с програмой
Вложения
Тип файла: rar Лаб 1.3.rar (1.96 Мб, 4 просмотров)
Олександr
0 / 0 / 0
Регистрация: 15.12.2013
Сообщений: 10
04.03.2014, 22:20  [ТС]     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #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;
}
НЕ КАТИТ(возникли ошибки сборки)
DrOffset
6460 / 3834 / 885
Регистрация: 30.01.2014
Сообщений: 6,629
04.03.2014, 23:31     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #16
Олександr, скачал твой проект, запустил - работает все нормально.
Версия Visual Studio какая? Может попробовать ее переустановить?
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
05.03.2014, 00:03     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #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 Посмотреть сообщение
НЕ КАТИТ(возникли ошибки сборки)
может покажешь какие?
UnsKneD
алкокодер
 Аватар для UnsKneD
153 / 149 / 11
Регистрация: 27.12.2012
Сообщений: 548
05.03.2014, 04:48     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #18
Цитата Сообщение от Олександr Посмотреть сообщение
НЕ КАТИТ(возникли ошибки сборки)
студию не обновляли? другую студию поверх этой не ставили?
zer0mail
2188 / 1871 / 187
Регистрация: 03.07.2012
Сообщений: 6,661
Записей в блоге: 1
05.03.2014, 14:04     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #19
Цитата Сообщение от ValeryS Посмотреть сообщение
Сообщение от zer0mail
Решения "в лоб" не дадут логарифмической сложности. Интересно, операции разрядного сдвига вправо/влево допустимы?
а если нет?
то можно использовать умножение на 2
Если нет, то придется складывать и "складывать сложенное" При аккуратной работе можно обойтись и без деления. Но неясно, какой уровень подготовки предполагает это задание.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.03.2014, 14:17     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность
Еще ссылки по теме:

C++ Возвести число в 10 степень, используя только четыре операции умножения
Возведение в степень числа используя рекурсию и операцию сложения C++
C++ Используя do while перемножить вводимые числа

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

Или воспользуйтесь поиском по форуму:
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
05.03.2014, 14:17     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность #20
Цитата Сообщение от zer0mail Посмотреть сообщение
При аккуратной работе можно обойтись и без деления.
как?
вот с делением я показал как реализовать лог. зависимость
Цитата Сообщение от zer0mail Посмотреть сообщение
то придется складывать и "складывать сложенное"
не понял переведи
Yandex
Объявления
05.03.2014, 14:17     Используя рекурсию, перемножить 2 натуральных числа не используя операции умножения и иметь логарифмическую сложность
Ответ Создать тему
Опции темы

Текущее время: 04:39. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru