# 给定一个数字作为字符串，找到连续递归加起来为9的连续子序列数

2021年4月3日17:38:54 发表评论 568 次浏览

## 本文概述

7 + 2 + 9 = 18

18递归

1 + 8 = 9

``````Input: 4189
Output: 3
There are three substrings which recursively add to 9.
The substrings are 18, 9 and 189.

Input: 999
Output: 6
There are 6 substrings which recursively add to 9.
9, 99, 999, 9, 99, 9``````

## C ++

``````// C++ program to count substrings with recursive sum equal to 9
#include <iostream>
#include <cstring>
using namespace std;

int count9s( char number[])
{
int count = 0; // To store result
int n = strlen (number);

// Consider every character as beginning of substring
for ( int i = 0; i < n; i++)
{
int sum = number[i] - '0' ;  //sum of digits in current substring

if (number[i] == '9' ) count++;

// One by one choose every character as an ending character
for ( int j = i+1; j < n; j++)
{
// Add current digit to sum, if sum becomes multiple of 5
// then increment count. Let us do modular arithmetic to
// avoid overflow for big strings
sum = (sum + number[j] - '0' )%9;

if (sum == 0)
count++;
}
}
return count;
}

// driver program to test above function
int main()
{
cout << count9s( "4189" ) << endl;
cout << count9s( "1809" );
return 0;
}``````

## Java

``````// Java program to count
// substrings with
// recursive sum equal to 9
import java.io.*;

class GFG
{
static int count9s(String number)
{
// To store result
int count = 0 ;
int n = number.length();

// Consider every character
// as beginning of substring
for ( int i = 0 ; i < n; i++)
{
// sum of digits in
// current substring
int sum = number.charAt(i) - '0' ;

if (number.charAt(i) == '9' )
count++;

// One by one choose
// every character as
// an ending character
for ( int j = i + 1 ;
j < n; j++)
{
// sum, if sum becomes
// multiple of 5 then
// increment count. Let
// us do modular arithmetic
// to avoid overflow for
// big strings
sum = (sum +
number.charAt(j) -
'0' ) % 9 ;

if (sum == 0 )
count++;
}
}
return count;
}

// Driver Code
public static void main (String[] args)
{
System.out.println(count9s( "4189" ));
System.out.println(count9s( "1809" ));
}
}

// This code is contributed
// by anuj_67.``````

## Python 3

``````# Python 3 program to count substrings
# with recursive sum equal to 9

def count9s(number):

count = 0 # To store result
n = len (number)

# Consider every character as
# beginning of substring
for i in range (n):

# sum of digits in current substring
sum = ord (number[i]) - ord ( '0' )

if (number[i] = = '9' ):
count + = 1

# One by one choose every character
# as an ending character
for j in range (i + 1 , n):

# Add current digit to sum, if
# sum becomes multiple of 5 then
# increment count. Let us do
# modular arithmetic to avoid
# overflow for big strings
sum = ( sum + ord (number[j]) -
ord ( '0' )) % 9

if ( sum = = 0 ):
count + = 1
return count

# Driver Code
if __name__ = = "__main__" :

print (count9s( "4189" ))
print (count9s( "1809" ))

# This code is contributed by ita_c``````

## C#

``````// C# program to count
// substrings with
// recursive sum equal to 9
using System;
class GFG
{
static int count9s(String number)
{
// To store result
int count = 0;
int n = number.Length;

// Consider every character
// as beginning of substring
for ( int i = 0; i < n; i++)
{
// sum of digits in
// current substring
int sum = number[i] - '0' ;

if (number[i] == '9' )
count++;

// One by one choose
// every character as
// an ending character
for ( int j = i + 1;
j < n; j++)
{
// sum, if sum becomes
// multiple of 5 then
// increment count. Let
// us do modular arithmetic
// to avoid overflow for
// big strings
sum = (sum + number[j] -
'0' ) % 9;

if (sum == 0)
count++;
}
}
return count;
}

// Driver Code
public static void Main ()
{
Console.WriteLine(count9s( "4189" ));
Console.WriteLine(count9s( "1809" ));
}
}

// This code is contributed
// by anuj_67.``````

## 的PHP

``````<?php
// PHP program to count substrings
// with recursive sum equal to 9

function count9s( \$number )
{
// To store result
\$count = 0;
\$n = strlen ( \$number );

// Consider every character as
// beginning of substring
for ( \$i = 0; \$i < \$n ; \$i ++)
{
//sum of digits in
// current substring
\$sum = \$number [ \$i ] - '0' ;

if ( \$number [ \$i ] == '9' ) \$count ++;

// One by one choose every character
// as an ending character
for ( \$j = \$i + 1; \$j < \$n ; \$j ++)
{

// Add current digit to sum, // if sum becomes multiple of 5
// then increment count. Let us
// do modular arithmetic to
// avoid overflow for big strings
\$sum = ( \$sum + \$number [ \$j ] - '0' ) % 9;

if ( \$sum == 0)
\$count ++;
}
}
return \$count ;
}

// Driver Code
echo count9s( "4189" ), "\n" ;
echo count9s( "1809" );

// This code is contributed by ajit
?>``````

``````3
5`````` 