Câini&Pisici

Problemă:

Să se aranjeze în toate modurile n pisici și m câini astfel încât nicio pisică sa nu fie așezată între 2 câini.

Implementare:

Cod Sursa C++

#include "stdafx.h"
#include<iostream>
 
using namespace std;
 
int x[100], pus[100], n, m, nr = 0;
 
void Write()
{
	for (int i = 1; i <= n + m; i++) if (x[i] == 1) cout << "P ";
	else cout << "C ";
	cout << endl;
	nr++;
}
 
int cond(int k)
{
	int c = 0, p = 0, i;
	for (i = 1; i <= k; i++)
	if (x[i] == 0) c++;
	else p++;
	if (p>n || c>m) return 0;
	if (k >= 3) if (x[k - 2] == 0 && x[k - 1] == 1 && x[k] == 0) return 0;
	return 1;
}
 
void Sub(int k)
{
	for (int i = 1; i >= 0; i--)
	{
		x[k] = i;
		if (cond(k))
		if (k == n + m) Write();
		else Sub(k + 1);
	}
}
int main()
{
	cout << "dati numarul de pisici: ";
	cin >> n;
	cout << "dati numarul de caini: ";
	cin >> m;
	Sub(1);
	cout << "Numarul solutiilor: "<<nr<<endl;
	system("pause");
	return 0;
}

Cod Sursa VB

Module Module1
    Dim x(100) As Integer
    Dim pus(100) As Integer
    Dim n As Integer = 0
    Dim m As Integer = 0
    Dim nr As Integer = 0
 
    Sub Write()
        Dim i As Integer
        For i = 1 To n + m
            If x(i) = 1 Then
                Console.Write("P ")
            Else
                Console.Write("C ")
            End If
        Next
        Console.WriteLine()
        nr += 1
    End Sub
 
    Function cond(ByVal k As Integer)
        Dim c As Integer = 0
        Dim p As Integer = 0
        Dim i As Integer
        For i = 1 To k
            If (x(i) = 0) Then
                c += 1
            Else
                p += 1
            End If
        Next
        If (p > n Or c > m) Then
            Return 0
        End If
        If k >= 3 Then
            If (x(k - 2) = 0 And x(k - 1) = 1 And x(k) = 0) Then
                Return 0
            End If
        End If
        Return 1
    End Function
 
    Sub Subrutina(ByVal k As Integer)
        Dim i As Integer
        For i = 1 To 0 Step -1
            x(k) = i
            If (cond(k)) Then
                If k = n + m Then
                    Write()
                Else : Subrutina(k + 1)
                End If
            End If
        Next
 
    End Sub
 
    Sub Main()
        Console.WriteLine("Dati numarul de pisici: ")
        n = Convert.ToInt32(Console.ReadLine())
        Console.WriteLine("Dati numarul de caini: ")
        m = Convert.ToInt32(Console.ReadLine())
        Subrutina(1)
        Console.WriteLine("Numarul solutiilor: " & nr)
        Console.ReadKey()
    End Sub
 
End Module

 

Rezultat: