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

Перевести программу с паскаля на с++ - C++

Восстановить пароль Регистрация
 
Lilechka
0 / 0 / 0
Регистрация: 08.04.2013
Сообщений: 25
03.06.2013, 15:05     Перевести программу с паскаля на с++ #1
Помогите перевести эту программу на с++, а то я паскаль не знаю, а программа именно та, которая мне нужна, тут и алгоритм расписан, переведите пожалуйста))

Рассмотрим все последовательности десятичных цифр четной длины (будем называть их номерами). Назовем номер счастливым, если сумма цифр в первой половине этого номера совпадает с суммой цифр во второй половине. Требуется определить количество счастливых номеров длины 2N.

Зафиксируем число K - сумму цифр в первой половине нашего номера. Ясно, что 0<=K<=9N. Пусть у нас есть таблица A такая, что A[i,j] - количество номеров длины i, сумма цифр которых равна j. Ясно, что для любого фиксированного K количество счастливых номеров равно A[N,K]^2 (действительно, мы можем выбрать левую и правую часть нашего номера независимо каждую из A[N,K] вариантов). Значит, искомое число равно сумме чисел A[N,K]^2 при K от 0 до 9N, и для решения задачи достаточно построить таблицу A.

Ясно, что при j>9*i или при j<0 мы имеем A[i,j]=0. Заметим, что A[1,i] равно 1 при 0<=i<=9 (есть только один номер длины 1, начинающийся на данную цифру - сама цифра). Теперь, пусть мы вычислили значения A[i,j] для всех i, меньших некоторого числа a, и нам требуется вычислить A[a,b]. Пусть T[a,b,c] - количество номеров длины a с суммой цифр b, последняя цифра которых равна c. Ясно, что T[a,b,c]=A[a-1,b-c], так как при отбрасывании последней цифры длина номера уменьшится на единицу, а сумма его цифр - на c. Теперь, A[a,b]=T[a,b,0]+T[a,b,1]+...+T[a,b,9], или A[a,b]=A[a-1,b]+A[a-1,b-1]+...+A[a-1,b-9]. Таким образом мы вычислим таблицу A.

Реализация алгоритма:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const
  MaxN = 5;
 
var
  A : array [1 .. MaxN,0 .. 9*MaxN] of Longint;
 
function Din_Example_2(N : Integer) : Longint;
var
  I,J,K : Integer;
  Res : Longint;
begin
  fillchar(A,sizeof(A),0);
  for I:=0 to 9 do
    A[1,I]:=1;
  for I:=2 to N do
    for J:=0 to 9*I do
      for K:=0 to 9 do
        if J>=K then
          A[I,J] := A[I,J] + A[I-1,J-K];
  Res := 0;
  for K:=0 to N*9 do
    Res := Res+A[N,K]*A[N,K];
  Din_Example_2 := Res;
end;
Например, при N=3 данный алгоритм выдаст ответ 55252.

Легко понять, что алгоритм требует O(N^2) времени и O(N^2) памяти.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.06.2013, 15:05     Перевести программу с паскаля на с++
Посмотрите здесь:

Перевести эту программу на С++ с паскаля C++
Нужно перевести программу из Паскаля в С++ C++
Надо перевести программу из ПАСКАЛЯ в СИ C++
C++ перевести программу из паскаля в с++(для среды Borland C++)
перевести программу из паскаля в с++ (для среды Borland C++). Дана матрица размера MxN. Поменять местами столбец с номером N и первый из столбцов C++
C++ помогите перевести программу с паскаля на С++
C++ Перевести программу с Паскаля на Си++
Нужно перевести программу из Паскаля в С++ C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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