本文概述
- C ++
- Java
- Python3
- C#
- 的PHP
例子：
输入：N = 2, L = 1, R = 3方法：这个想法是找到分别在L和R之间具有0和1模2的余数的计数。可以通过以下方式计算该计数：
输出：5可能所有元素之和被2整除的数组为[1、1], [2、2], [1、3], [3、1]和[3, 3]
输入：N = 3, L = 2, R = 2
输出：1
我们需要对余数为1模2的范围之间的数字进行计数。F =所需类型范围内的第一个数字L =所需类型范围内的最后一个数字Count =(L – F)/ 2 cnt0, 而cnt1表示介于每种类型。然后，利用动态规划来解决这一问题。设dp[i][j]表示第一个i数模2等于j的路径数。假设我们需要计算dp[i][0]，那么它将有如下递归关系:dp[i][0] = (cnt0 * dp[i - 1][0] + cnt1 * dp[i - 1][1])。第一项表示在(i - 1)之前余数为0的方式的数量，因此我们可以将cnt0数字放在第i个位置，使余数之和仍然为0。第二项表示到(i - 1)为止余数之和为1的方式数，因此我们可以将cnt1数放在第i个位置，使余数之和为0。同样，我们可以计算dp[i][1]。
最终答案用dp[N][0]表示。
下面是上述方法的实现：
C ++
//C++ implementation of the approach
#include <
bits/stdc++.h>
using namespace std;
//Function to return the number of ways to
//form an array of size n such that sum of
//all elements is divisible by 2
int countWays( int n, int l, int r)
{
int tL = l, tR = r;
//Represents first and last numbers
//of each type (modulo 0 and 1)
int L[2] = { 0 }, R[2] = { 0 };
L[l % 2] = l, R[r % 2] = r;
l++, r--;
if (l <
= tR &
&
r>
= tL)
L[l % 2] = l, R[r % 2] = r;
//Count of numbers of each type between range
int cnt0 = 0, cnt1 = 0;
if (R[0] &
&
L[0])
cnt0 = (R[0] - L[0]) /2 + 1;
if (R[1] &
&
L[1])
cnt1 = (R[1] - L[1]) /2 + 1;
int dp[n][2];
//Base Cases
dp[1][0] = cnt0;
dp[1][1] = cnt1;
for ( int i = 2;
i <
= n;
i++) {//Ways to form array whose sum upto
//i numbers modulo 2 is 0
dp[i][0] = (cnt0 * dp[i - 1][0]
+ cnt1 * dp[i - 1][1]);
//Ways to form array whose sum upto
//i numbers modulo 2 is 1
dp[i][1] = (cnt0 * dp[i - 1][1]
+ cnt1 * dp[i - 1][0]);
}//Return the required count of ways
return dp[n][0];
}//Driver Code
int main()
{
int n = 2, l = 1, r = 3;
cout <
<
countWays(n, l, r);
return 0;
}Java
//Java implementation of the approach
class GFG
{//Function to return the number of ways to
//form an array of size n such that sum of
//all elements is divisible by 2
static int countWays( int n, int l, int r)
{
int tL = l, tR = r;
//Represents first and last numbers
//of each type (modulo 0 and 1)
int [] L = new int [ 3 ];
int [] R = new int [ 3 ];
L[l % 2 ] = l;
R[r % 2 ] = r;
l++;
r--;
if (l <
= tR &
&
r>
= tL)
{
L[l % 2 ] = l;
R[r % 2 ] = r;
}//Count of numbers of each type between range
int cnt0 = 0 , cnt1 = 0 ;
if (R[ 0 ]>
0 &
&
L[ 0 ]>
0 )
cnt0 = (R[ 0 ] - L[ 0 ]) /2 + 1 ;
if (R[ 1 ]>
0 &
&
L[ 1 ]>
0 )
cnt1 = (R[ 1 ] - L[ 1 ]) /2 + 1 ;
int [][] dp = new int [n + 1 ][ 3 ];
//Base Cases
dp[ 1 ][ 0 ] = cnt0;
dp[ 1 ][ 1 ] = cnt1;
for ( int i = 2 ;
i <
= n;
i++)
{//Ways to form array whose sum upto
//i numbers modulo 2 is 0
dp[i][ 0 ] = (cnt0 * dp[i - 1 ] [ 0 ]
+ cnt1 * dp[i - 1 ][ 1 ]);
//Ways to form array whose sum upto
//i numbers modulo 2 is 1
dp[i][ 1 ] = (cnt0 * dp[i - 1 ][ 1 ]
+ cnt1 * dp[i - 1 ][ 0 ]);
}//Return the required count of ways
return dp[n][ 0 ];
}//Driver Code
public static void main(String[] args)
{
int n = 2 , l = 1 , r = 3 ;
System.out.println(countWays(n, l, r));
}
}//This code is contributed by Code_Mech.Python3
# Python3 implementation of the approach# Function to return the number of ways to
# form an array of size n such that sum of
# all elements is divisible by 2
def countWays(n, l, r):tL, tR = l, r# Represents first and last numbers
# of each type (modulo 0 and 1)
L = [ 0 for i in range ( 2 )]
R = [ 0 for i in range ( 2 )]L[l % 2 ] = l
R[r % 2 ] = rl + = 1
r - = 1if (l <
= tR and r>
= tL):
L[l % 2 ], R[r % 2 ] = l, r# Count of numbers of each type
# between range
cnt0, cnt1 = 0 , 0
if (R[ 0 ] and L[ 0 ]):
cnt0 = (R[ 0 ] - L[ 0 ]) //2 + 1
if (R[ 1 ] and L[ 1 ]):
cnt1 = (R[ 1 ] - L[ 1 ]) //2 + 1dp = [[ 0 for i in range ( 2 )]
for i in range (n + 1 )]# Base Cases
dp[ 1 ][ 0 ] = cnt0
dp[ 1 ][ 1 ] = cnt1
for i in range ( 2 , n + 1 ):# Ways to form array whose sum
# upto i numbers modulo 2 is 0
dp[i][ 0 ] = (cnt0 * dp[i - 1 ][ 0 ] +
cnt1 * dp[i - 1 ][ 1 ])# Ways to form array whose sum upto
# i numbers modulo 2 is 1
dp[i][ 1 ] = (cnt0 * dp[i - 1 ][ 1 ] +
cnt1 * dp[i - 1 ][ 0 ])# Return the required count of ways
return dp[n][ 0 ]# Driver Code
n, l, r = 2 , 1 , 3
print (countWays(n, l, r))# This code is contributed
# by Mohit KumarC#
//C# implementation of the approachusing System;
class GFG
{//Function to return the number of ways to
//form an array of size n such that sum of
//all elements is divisible by 2
static int countWays( int n, int l, int r)
{
int tL = l, tR = r;
//Represents first and last numbers
//of each type (modulo 0 and 1)
int [] L = new int [3];
int [] R = new int [3];
L[l % 2] = l;
R[r % 2] = r;
l++;
r--;
if (l <
= tR &
&
r>
= tL)
{
L[l % 2] = l;
R[r % 2] = r;
}//Count of numbers of each type between range
int cnt0 = 0, cnt1 = 0;
if (R[0]>
0 &
&
L[0]>
0)
cnt0 = (R[0] - L[0]) /2 + 1;
if (R[1]>
0 &
&
L[1]>
0)
cnt1 = (R[1] - L[1]) /2 + 1;
int [, ] dp= new int [n + 1, 3];
//Base Cases
dp[1, 0] = cnt0;
dp[1, 1] = cnt1;
for ( int i = 2;
i <
= n;
i++)
{//Ways to form array whose sum upto
//i numbers modulo 2 is 0
dp[i, 0] = (cnt0 * dp[i - 1, 0]
+ cnt1 * dp[i - 1, 1]);
//Ways to form array whose sum upto
//i numbers modulo 2 is 1
dp[i, 1] = (cnt0 * dp[i - 1, 1]
+ cnt1 * dp[i - 1, 0]);
}//Return the required count of ways
return dp[n, 0];
}//Driver Code
static void Main()
{
int n = 2, l = 1, r = 3;
Console.WriteLine(countWays(n, l, r));
}
}//This code is contributed by mits的PHP
<
?php
//PHP implementation of the approach //Function to return the number of ways to
//form an array of size n such that sum of
//all elements is divisible by 2
function countWays( $n , $l , $r )
{
$tL = $l ;
$tR = $r ;
$L = array_fill (0, 2, 0);
$R = array_fill (0, 2, 0);
//Represents first and last numbers
//of each type (modulo 0 and 1)
$L [ $l % 2] = $l ;
$R [ $r % 2] = $r ;
$l ++;
$r --;
if ( $l <
= $tR &
&
$r>
= $tL )
{
$L [ $l % 2] = $l ;
$R [ $r % 2] = $r ;
}//Count of numbers of each type
//between range
$cnt0 = 0;
$cnt1 = 0;
if ( $R [0] &
&
$L [0])
$cnt0 = ( $R [0] - $L [0]) /2 + 1;
if ( $R [1] &
&
$L [1])
$cnt1 = ( $R [1] - $L [1]) /2 + 1;
$dp = array ();
//Base Cases
$dp [1][0] = $cnt0 ;
$dp [1][1] = $cnt1 ;
for ( $i = 2;
$i <
= $n ;
$i ++)
{ //Ways to form array whose sum upto
//i numbers modulo 2 is 0
$dp [ $i ][0] = ( $cnt0 * $dp [ $i - 1][0] +
$cnt1 * $dp [ $i - 1][1]);
//Ways to form array whose sum upto
//i numbers modulo 2 is 1
$dp [ $i ][1] = ( $cnt0 * $dp [ $i - 1][1] +
$cnt1 * $dp [ $i - 1][0]);
} //Return the required count of ways
return $dp [ $n ][0];
} //Driver Code
$n = 2;
$l = 1;
$r = 3;
echo countWays( $n , $l , $r );
//This code is contributed by Ryuga
?>
【形成具有给定范围内的整数的数组的方法，以使总和可被2整除】输出如下：
5推荐阅读
- Django教程详细指南介绍
- 如何开始软件测试职业-完整指南！
- 十进制等效项大于或等于K的子字符串的计数
- PHP stream_get_transports()函数用法示例
- 修改给定数组以使奇数和偶数索引元素的总和相同
- 从OpenCV 2到OpenCV 3.x的过渡
- AWS中安全组和网络ACL之间的区别
- 8085程序以n个数字的数组搜索数字
- Android测试（从零开始3—— Instrumented单元测试1）