[Algorithm – Java]Share loose use Go back
Recommended articles listed requirements may cases when the amount of N divided into a denomination coins[in].
import java.util.Scanner;
class java_chiatien
{
int n, N, a[], b[], sum=0;
public void input()
{
Scanner in = new Scanner(System.in);
System.out.print("Nhap so tien can chia: ");
N = in.nextInt();
System.out.print("Nhap so loai tien le: ");
n = in.nextInt();
a = new int [n];
b = new int [N];
for (int i=0; i<n; i++)
{
System.out.printf("Nhap loai tien thu %d : ",i+1);
a[i] = in.nextInt();
}
in.close();
}
public void chiatien(int i)
{
for (int k = 0; k < n; k++)
{
b[i] = a[k];
if (i==0 || (i >0 && b[i] >= b[i-1]))
{
sum += b[i];
if (sum <= N)
{
if (sum == N)
{
for (int l=0; l<=i; l++)
System.out.print(b[l]+ " ");
System.out.print("n");
}
else
chiatien(i+1);
}
sum -= b[i];
}
}
}
public static void main(String[] agrs)
{
java_chiatien ct = new java_chiatien();
ct.input();
System.out.print("nCac cach chia tien :n");
ct.chiatien(0);
}
}
Another way for similar articles:
Let's count the ways analysis of N ( N<=100000 ) the sum of positive integers.
Noted 2 the only difference is the way the numbers are considered the same class. Example 4 have 5 analyzing later:
4 = 1 + 1 + 1 + 1
4 = 1 + 1 + 2
4 = 1 + 3
4 = 2 + 2
4 = 4
Two-way analysis 4 = 1 + 3 = 3 + 1 are only counted once.
Since the results will be great so you only need to put the remainder of the division of ways for Other 1000000000 ( 10^9 ).
Input
A single natural number N.
Output
In the remainder of the number of ways to find the 10 ^ 9.
Example
Input:
4
Output:
5
uses crt; var a: array[1..10000] of 0..9; n, i, j: longint; procedure print(vitri: integer); begin write(n,' = '); for j:= 1 to vitri do if j= vitri then write(a[j]) else write(a[j],' + '); writeln; end; begin clrscr; write('Nhap n: '); readln(n); for i:= 1 to n do a[i]:= 1; print(i); i:= n; while a[1] &lt;&gt; n do begin a[i-1]:= a[i-1] + a[i]; dec(i); print(i); if i&gt;1 then while (a[i]-a[i-1] &gt;= 2) do begin dec(a[i]); inc(a[i-1]); print(i); end; end; readln end.Reference code from you tranminhchien at codevn.org
I read the code but did not fully understand.
Can you talk about where to go back and split the money?