Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Севак
любитель покушать
682 / 633 / 106
Регистрация: 25.09.2011
Сообщений: 1,313
#1

Перевод кода с Java - C++

06.07.2013, 20:46. Просмотров 1263. Ответов 28
Метки нет (Все метки)

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

Java
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
import java.math.BigInteger;
import java.util.Scanner;
 
public class Main {
    public static final BigInteger one = BigInteger.ONE;
    public static final BigInteger minusOne = BigInteger.valueOf(-1);
    public static final BigInteger two = BigInteger.valueOf(2);
    public static final BigInteger three = BigInteger.valueOf(3);
    public static final BigInteger mod = BigInteger.valueOf(1000000007);
 
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        System.out.println(G(n));
    }
 
    public static BigInteger G(int n) {
        if(n % 2 == 0) {
            return two.shiftLeft(n).add(one).divide(three).mod(mod).subtract(one);
        } else {
            return two.shiftLeft(n).add(minusOne).divide(three).mod(mod);
        }
    }
 
}
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
#include <iostream>
#include <stdint.h>
#include <math.h>
 
using namespace std;
 
int64_t G(int64_t n, int64_t mod) {
    if(n % 2 == 0) {
        return (((2 << n) + 1)/3) % mod - 1;
    } else {
        return (((2 << n) - 1)/3) % mod;
    }
}
 
 
int main() {
    int64_t n;
    int64_t mod = 1000000007;
 
    cin >> n;
    cout << G(n, mod);
 
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.07.2013, 20:46
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Перевод кода с Java (C++):

Перевод кода с Java на С++ - C++
Помогите перевести следующий код с Java на C++: * Вызывающий класс*/ public class Main{ public static void main(String args){ ...

Перевод кода с Java на С++ - C++
Такой вот код нужно перевести. import java.io.*; import java.math.BigInteger; import java.util.*; public class Main { /** *...

Перевод кода из java в С++ - C++
Делаю попытку создать хоть какую то стратегию http://russianaicup.ru/post/2#comment-926 ,помогите перевести код на с++. Или хотя бы как...

Перевод кода с Java на С++ - C++
Помогите перевести следующий код с Java на C++: import java.io.File; import java.io.IOException; import java.util.Scanner; ...

Перевод кода с Java - C++
Здравствуйте! Есть кусок кода на java, в котором идет работа с map, пробовал переписать самостоятельно, но ничего хорошего из этого не...

Перевод кода - C++
Переведите пжалуйста код на паскаль #include&lt;iostream&gt; #include&lt;string&gt; using namespace std; unsigned long long res=1; int n,len;...

28
Thinker
Эксперт С++
4231 / 2205 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.07.2013, 21:37 #16
Цитата Сообщение от Dani Посмотреть сообщение
Thinker, что? переводить не нужно ничего.
я про эту задачу
Возведение двойки в миллиардную степень
немного похожая задача
1
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
06.07.2013, 21:39 #17
Двоичное возведение в степень строится по следующему принципу. Есть функция http://www.cyberforum.ru/cgi-bin/latex.cgi?power(a, b) , если b - четное, то из числа http://www.cyberforum.ru/cgi-bin/latex.cgi?power(a, b) можно извлечь корень, получается, что http://www.cyberforum.ru/cgi-bin/latex.cgi?power(a, b) = {(power(a, b/2))}^{2} . Если же b нечетное, то http://www.cyberforum.ru/cgi-bin/latex.cgi?power(a, b) = power(a, b-1) * a . При b = 1 , результат равен a.

Ничего кроме умножения и рекурсивного спуска.
1
Thinker
Эксперт С++
4231 / 2205 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.07.2013, 21:42 #18
Dani, это да, очень даже понятно но та задача даже так быстро не решается. я там оценил время работы алгоритма. если использовать двоичное возведение, то оно даст выигрыш не более чем в 10 раз и время работы будет сутками исчисляться
1
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
06.07.2013, 21:45 #19
Хм... щас... может Карацуба
http://www.wolframalpha.com/input/?i=2%5E1000000000
2
Thinker
Эксперт С++
4231 / 2205 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.07.2013, 21:46 #20
Цитата Сообщение от Dani Посмотреть сообщение
Хм... щас... может Карацуба
умножение по методу Карацубы тоже хорошо известная и полезная вещь, но увы...
1
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
06.07.2013, 21:49 #21
http://habrahabr.ru/post/124258/

Карацуба дает сложность http://www.cyberforum.ru/cgi-bin/latex.cgi?{n}^{{log}_{2}3} от числа цифр. Двоичное возведение дает 31. Это скрытая константа, что вполне приемлемо. Итого 3.0103 * 10^8
2
Севак
любитель покушать
682 / 633 / 106
Регистрация: 25.09.2011
Сообщений: 1,313
06.07.2013, 21:53  [ТС] #22
Я тут посмотрел, со своим Java'вским кодом на 1_000_000_000 получаю такие результаты:

1000000000
Time: 1.283588667 sec
93750000
Мне нужно уложиться в 1 секунду, поэтому пойду-ка я оптимизировать его, наверное больше времени потрачу на поиск решения на c++
0
Thinker
Эксперт С++
4231 / 2205 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.07.2013, 21:54 #23
ладно, может зря отверг эту идею, думал есть какой то красивый мат.метод
2
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
06.07.2013, 21:57 #24
Севак, там есть реализация Карацубы на С++ и добавь к этому двоичное возведение в степень. Буду признателен, если скажешь, за сколько выполнится.

Добавлено через 1 минуту

Не по теме:

Цитата Сообщение от Thinker Посмотреть сообщение
ладно, может зря отверг эту идею, думал есть какой то красивый мат.метод
получается, только хардкор

1
Севак
любитель покушать
682 / 633 / 106
Регистрация: 25.09.2011
Сообщений: 1,313
06.07.2013, 22:02  [ТС] #25
Dani,

Не по теме:

хорошо только наверное не сегодня, с с++ 2ой день только работаю и то по необходимости, а задачу нужно сделать срочно

0
diagon
Higher
1936 / 1202 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
07.07.2013, 03:34 #26
Вроде ж все тривиально
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
#include <iostream>
 
unsigned powmod(unsigned base, unsigned exp, unsigned modulo) //returns (base ^ exp) % modulo
{
    unsigned res = 1;
    
    while (exp != 0) 
    {
        if ((exp & 1) != 0)
        {
            res = (1ll * res * base) % modulo;
        }
        
        base = (1ll * base * base) % modulo;
        exp >>= 1;
    }
    
    return res;
}
 
int G(int n, int modulo) 
{
    return (-~powmod(2, n + 1, modulo) - 2 * (n & 1)) * 333333336ll % modulo + ~n % 2;
}
 
int main()
{
    int n;
    std::cin >> n;
    std::cout << G(n, 1000000007);
}
1
Севак
любитель покушать
682 / 633 / 106
Регистрация: 25.09.2011
Сообщений: 1,313
07.07.2013, 11:56  [ТС] #27
diagon,

Не по теме:

я б тебя прям расцеловал (ничего плохого не подумай)! спасибо большое!

0
Герц
524 / 341 / 4
Регистрация: 05.11.2010
Сообщений: 1,077
Записей в блоге: 1
07.07.2013, 12:05 #28
Есть код на java, который работает недостаточно быстро, для его ускорения решил переписать его на c++
Совет на будущее. Прежде чем что-то оптимизировать, нужно определить bottleneck'и, ты ведь даже не знаешь, в чем именно проблема. Может быть она в твоих руках? :-)
0
Севак
любитель покушать
682 / 633 / 106
Регистрация: 25.09.2011
Сообщений: 1,313
07.07.2013, 12:06  [ТС] #29
Герц, может быть
0
07.07.2013, 12:06
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.07.2013, 12:06
Привет! Вот еще темы с ответами:

Перевод кода в С - C++
Помогите, пожалуйста, перевести код: a = 0.99f; b = 1.f - a; Не знаю что это за язык и не могу понять значение f

Перевод кода - C++
Помогите пожалуйста перевести код с паскаля на си++. Пока получилось как-то так. #include &lt;iostream&gt; #include &lt;fstream&gt; #include...

перевод кода из С++ в С - C++
Кто может перевести код на С ,сделайте доброе дело.....Пожалуйста ;-) #include &lt;iostream&gt; #include &lt;iomanip&gt; #include &lt;time.h&gt; ...

Перевод кода с C# на С++ - C++
Есть код на C# нужно перевести на С++, помогите пожалуйста так как еще не свободно владею языками программирования. Буду очень благодарен. ...


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

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

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