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

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

Войти
Регистрация
Восстановить пароль
 
Lilechka
0 / 0 / 0
Регистрация: 08.04.2013
Сообщений: 25
#1

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

03.06.2013, 15:05. Просмотров 232. Ответов 0
Метки нет (Все метки)

Помогите перевести эту программу на с++, а то я паскаль не знаю, а программа именно та, которая мне нужна, тут и алгоритм расписан, переведите пожалуйста))

Рассмотрим все последовательности десятичных цифр четной длины (будем называть их номерами). Назовем номер счастливым, если сумма цифр в первой половине этого номера совпадает с суммой цифр во второй половине. Требуется определить количество счастливых номеров длины 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) памяти.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.06.2013, 15:05
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Перевести программу с паскаля на с++ (C++):

Перевести программу с Паскаля на Си++ - C++
Помогите пожалуйста переписать этот код на язык Си++, не знаю как также объявляется массив :( const a=3; b=4; var x,y,u:array...

Перевести программу с Паскаля на Си++ - C++
Помогите пожалуйста переписать этот код на язык Си++. Я просто не понимаю как его переписать. program Z2; const mx=1000; var a,b:...

Перевести эту программу на С++ с паскаля - C++
Кто может перевести эту программу на С++ вот задание 1 определит колличество строк без нуле 2 сложить характеристические ряды (это...

Помогите перевести программу с Паскаля на С++ - C++
function IsPowerN(K: integer; N: byte): boolean; var i: byte; res: integer; begin res := 1; //начальное значение степеня...

Надо перевести программу из ПАСКАЛЯ в СИ - C++
uses crt; var a:array of integer; m,n,i,j,k,m1,n1,q1,q2:integer; c:integer; begin clrscr; randomize; k:=0; ...

Нужно перевести программу из Паскаля в С++ - C++
Помогите пожалуйста перевести. Из Паскаля в С++ Код программы Паскаля: program Hello; var i:integer; begin ...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.06.2013, 15:05
Привет! Вот еще темы с ответами:

Нужно перевести программу из Паскаля в С++ - C++
К сожалению С++ только начали изучать, а программ задали много Delphi знаю хорошо Задача 1.Составить программу упорядочения по...

помогите перевести программу с паскаля на С++ - C++
Ребят , помогите перевести программу с паскаля на С++ , или подскажите как написать нечто подобное. Заранее благодарен. Вот задание : ...

перевести программу из паскаля в с++(для среды Borland C++) - C++
Помогите пожалуйста перевести программу из паскаля в с++(для среды Borland C++) Условие: дан символ С, изображающий цифру или...

перевести программу из паскаля в с++ (для среды Borland C++). Дана матрица размера MxN. Поменять местами столбец с номером N и первый из столбцов - C++
Помогите пожалуйста перевести программу из паскаля в с++(для среды Borland C++) Условие:дана матрица размера MxN. Поменять местами...


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

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

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