Anzahl der möglichen Wege der Zuweisung freie Grundstücke zu den Gebäuden mit der Einschränkung, dass keine zwei aufeinander folgenden Grundstücke vorhanden, auf denen es erlaubt ist, zu bauen

Verwenden Sie Rekursion. Ich bin mir nicht sicher über die Zeit, die Komplexität, da für die großen Eingang, es nimmt verdammt viel Zeit(tatsächlich hängt für große Werte). Für kleine Eingänge, die ich.e M < 10, so scheint es, Antworten zu geben.

#include <iostream>

using namespace std;

int recur(char c, int num, int N) {
if (num == N) {
    return 1;
}

if (num < N) {
    if (c == 'X') {
        return recur('Y', num + 1, N);
    } else {
        return (recur('X', num + 1, N) + recur('Y', num + 1, N));
    }
}
}

int main()
{
int N = 4;

//x is number of combinations when the first slot is used to build a house
int x = recur('X', 1, N);

//y is number of combinations when the first slot is left empty
int y = recur('Y', 1, N);

cout << "x = " << x << endl;
cout << "y = " << y << endl;

//Since same number exists on other side also
cout << "total = " << (x + y) * (x + y) << endl;

return 0;
}

Dieses problem bezieht sich auf Permutationen und Kombinationen, insbesondere binomial-theorem. Umfang ist jene, die gut darin sind, können Sie mathemical Gleichung für dieses problem und dann ist es einfach für jeden M als Eingang in die Gleichung.

Aber mit coding, python-Lösung:

from itertools import product
M = 7 #change as per need
cnt = 0
l = []

for w in product(['x','y'], repeat=M):
    tmp = ''.join(w)
    if 'xx' not in tmp:
        l.append(tmp)
        cnt += 1
print cnt*cnt
print l

output-Instanz:

1156
['xyxyxyx', 'xyxyxyy', 'xyxyyxy', 'xyxyyyx', 'xyxyyyy', 'xyyxyxy', 'xyyxyyx', 'xyyxyyy', 'xyyyxyx', 'xyyyxyy', 'xyyyyxy', 'xyyyyyx', 'xyyyyyy', 'yxyxyxy', 'yxyxyyx', 'yxyxyyy', 'yxyyxyx', 'yxyyxyy', 'yxyyyxy', 'yxyyyyx', 'yxyyyyy', 'yyxyxyx', 'yyxyxyy', 'yyxyyxy', 'yyxyyyx', 'yyxyyyy', 'yyyxyxy', 'yyyxyyx', 'yyyxyyy', 'yyyyxyx', 'yyyyxyy', 'yyyyyxy', 'yyyyyyx', 'yyyyyyy']

So, das löst das problem. Wenn es unerwartete Ausgabe für große M, bitte Kommentar posten.

Ich denke Rekursion wäre die beste Lösung für dieses problem.
Meine Idee ist, zu denken, über einen Baum, der gebildet werden kann, mit der Tiefe M, Bei der letzten Zählung die Anzahl der Blattknoten im Baum.
Das ist nur eine Idee, die Eigentliche Rekursion gestartet werden kann durch das denken, ob der erste Ort X oder nicht. Es kann sowohl X & Y nur, wenn es die Eltern(frühere Handlung) getroffen hat, Y. Aber, wenn es die Eltern genommen hat X, es kann nur in Y.
Mit dieser Idee machte ich eine Rekursion wie.

int count=0; //Maintain a global counter to count the leaves
void fun(bool xTaken, int M)

{

     if(M==0)
     {
        count++; //We've reached the leaf
        return;
     }

     if(xTaken==false)
     {
        //We can take X
        fun(true,M-1);

        //or we can take Y
        fun(false,M-1);
     }

     else if(xTaken==true)
     {
        //We can only take Y
        fun(false,M-1);
     }

}

Und unsere Antwort wird sein, count*count.
Wieder können wir optimieren diese Rekursion durch die Pflege von doppelten Rekursion mithilfe von memoization

Ich bin mir nicht sicher, ob dies die effizienteste Lösung, aber geht hier
Für einen gegebenen Wert m, so wird die gesamte Anzahl der erforderlichen Regelungen sind:

r=1;sum=0;

while(m>=r)
{

    sum+=mCr;

    m--;

    r++;

}

wenn beispielsweise m=7
ans= 7C1 + 6C2 + 5C3 + 4C4 ;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.HashMap;

public class KingKohima 
{

    public static void main(String[] args) throws Exception

    {
        BigInteger a = new BigInteger("2");
        BigInteger b = new BigInteger("3");
        BigInteger result = new BigInteger("0");


        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(br.readLine());
        if(m<=0)
        {
            System.out.println("0");
        }
        else if(m==1)
        {
            System.out.println("2");
        }
        else if(m==2)
        {
            System.out.println("3");
        }
        else
        {
            Integer i=new Integer(3);

            for(;i<=m;i++)
            {
                result = a.add(b);
                a=new BigInteger(b.toString());
                b=new BigInteger(result.toString());

            }
        }

        System.out.println(result.multiply(result));

    }

}