Recently, I have done a lot of problems in mathematics , It's settled The basis of number theory , linear algebra ( Only the matrix , The determinant holds the pit ), Combinatorial mathematics Some simple questions in . So the inevitable next step is to Game theory this philosophy Work starts in Tai Keng .

Of course , Because I am very happy food , So we can only start from the most basic and easiest part .

This time, we mainly introduce two basic models :Bash Game&&Nim Game, It's more classic

Let's start with

1.Bash Game

Bash Game( Bash Game ) It's a kind of Zero basis Introduction to the topic , Its basic model is like this :

A pile of stones n individual , They take turns taking stones from it , It is stipulated that at least one , Most take m individual , The last winner wins . Ask two people about the game , They all use the smartest strategies , Who will win in the end .

First of all, let's start from childhood :

  • When m>=n when , You can catch the stones first , such The first step is to win

  • When n=m+1 when , First hand, no matter how you catch it , Will stay 1~m A stone , In this way, you can finish it with one hand , such If you start, you'll lose

  • When m+1<n<2*(m+1) when , The first thing you need to do is grab the right stones and you'll have the rest m+1 A stone , And then you lose , that The first step is to win

  • When n=2*(m+1) when , The backhand can take this strategy , When you start x Time , Catch it in the back m+1-x individual , This will put m+1 I'd like to give you the first hand , that If you start, you'll lose

  • ......

So from the above analysis, we can easily conclude that : When n%(m+1)==0 when , If you start, you'll lose ; Otherwise, the first player will win

This is very simple , Because who will face it first k*(m+1)(k As a positive integer ) This situation is bound to fail . Because one side can let you two get stones and for each time m+1 Cause the other side to fail .

There are still some distortions to this problem , The classic is : Take a number from 0 It's starting to grow , The scope of each increase is 1~k, Who first increases the number to n Just Win||Lose

This translates directly into Bash Game Just do it

Here are some examples &&CODE( The following examples are from HDU

1846

Bash The board problem of game , Just go straight on

CODE

#include<cstdio>
using namespace std;
int t,n,m;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
read(t);
while (t--)
{
read(n); read(m);
puts(n%(m+1)?"first":"second");
}
return 0;
}

2149

This is the case with the variant , We're doing a transformation. We're doing a transformation , As for the output scheme, we can make a special judgment

CODE

#include<cstdio>
using namespace std;
int n,m;
inline void write(int x)
{
if (x/10) write(x/10);
putchar(x%10+'0');
}
int main()
{
register int i;
while (scanf("%d%d",&m,&n)!=EOF)
{
if (n>=m)
{
for (i=m;i<n;++i)
write(i),putchar(' '); write(n); putchar('\n');
} else
if (m%(n+1)) write(m%(n+1)),putchar('\n'); else puts("none");
}
return 0;
}

2138

ditto ,Bash Game Just go straight on

CODE

#include<cstdio>
using namespace std;
int t,n,m;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
read(t);
while (t--)
{
read(n); read(m);
puts(n%(m+1)?"Grass":"Rabbit");
}
return 0;
}

4764

Pay attention to the greater than or equal to n You lose. , therefore n One less

CODE

#include<cstdio>
using namespace std;
int n,m;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (;;)
{
read(n); read(m);
if (!n&&!m) break;
puts((n-1)%(m+1)?"Tang":"Jiang");
}
return 0;
}

2.Nim Game

This is actually Bash Game The evolution of , But the depth of thinking has gone up several steps

First, let's look at the basic model :

There are... On the ground n Rubble , Each person can take out any number of stones from any pile of stones at a time and throw them away , You can finish it , Can't do without taking . You can only take it from a pile at a time . In the end, those who don't have a stone will lose . If a is the first , And tell you this n The number of stones , He wants to know if there is a winning strategy .

Isn't that complicated , First of all, let's consider the case of small data :

  • When there's only a pile of stones , Unless there are no stones , Otherwise, we can grasp it first

  • When there are two piles of stones , The backhand only needs to follow the action of the forehand

  • ......( I can't figure out what's going on )

But before us, there was a great God who successfully proved that The magic conclusion

When n The number of heaps of stones is equal to 0 when , If you start, you'll lose , Otherwise, the first player will win

Please move to attack dalao's blog

I'm confused, right? In fact, I'm also , So let's Perceptual understanding once ( The following description is for personal understanding only , Hardly any Any theoretical basis , Please choose to read )

First of all, because it's all 0 I failed when I was young , So we can think that when their XOR sum is 0 Namely Be defeated

In this way, we can start with if XOR and for 0 Then you lose

If not , We can win in a dirty way ( That's the way it's mentioned above )

We can visualize it as And Bash Game First in the middle, first in the middle k*(m+1) And then by making and always for m+1 To win

And that's the magic Nim Game

Here's a template question Luogu P2197 nim game

Because it's naked Nim Game, Right here CODE 了

#include<cstdio>
using namespace std;
int t,n,x,tot;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
register int i; read(t);
while (t--)
{
for (read(n),tot=0,i=1;i<=n;++i)
read(x),tot^=x;
puts(tot?"Yes":"No");
}
return 0;
}

Of course, this is just the beginning of game theory , Something really powerful, like SG function &&MINMAX I'm still confused when I wait for something

Two basic models in game theory ——Bash Game&&Nim Game More articles about

  1. Talking about Java Medium equals and ==( turn )

    Talking about Java Medium equals and == In the beginning Java when , You may often encounter the following code : 1 String str1 = new String("hello"); 2 String str ...

  2. Talking about Linux Signal processing mechanism in ( Two )

    First of all, thank you @ Little brother Yao   This friend wrote an article to me last night < Talking about Linux Signal processing mechanism in ( One )> Correction , I used the previous topic “ elementary analysis ” The word" , It gives people a sense of dissecting the kernel . I know I'm not good enough , Not even to Lin ...

  3. Talking about Java Objects and references in

    Talking about Java Objects and object references in stay Java in , There is a group of nouns that often appear together , They are “ Objects and object references ”, Many friends are learning Java You may often confuse this 2 A concept , I think they're one thing , In fact, it's not . Today we're going to come together ...

  4. Talking about Java Medium equals and ==

    Talking about Java Medium equals and == In the beginning Java when , You may often encounter the following code : String str1 = new String("hello"); String str2 = ...

  5. turn 【】 Talking about sql Medium in And not in,exists And not exists The difference between _

    Talking about sql Medium in And not in,exists And not exists The difference between   1.in and exists in It's the exterior and the interior hash Connect , and exists It's external work loop loop , Every time loop Loop to internal table ...

  6. Talking about iOS Medium userAgent

    Talking about iOS Medium userAgent   User-Agent( The user agent ) The string is Web The browser is used to declare its own model version and follow HTTP Request sent to Web The string of the server , stay Web The string is available on the server . In the company ...

  7. Talking about JavaScript Closure in

    Talking about JavaScript Closure in stay JavaScript in , A closure is a function that : It has access to variables in the scope of another function . Common ways to create a closure : Create another function inside one function . such as : functio ...

  8. Talking about sql Medium in And not in,exists And not exists The difference between

    turn Talking about sql Medium in And not in,exists And not exists The difference between   12 month 12 Beijing, Japan OSC Yuan Chuang Hui —— Year end celebration of open source technology »   sql exists in 1.in and exists ...

  9. Talking about Java Deep and shallow copies in ( Reprint )

    Talking about Java Deep and shallow copies in ( Reprint ) Link to the original text : http://blog.csdn.net/tounaobun/article/details/8491392 Let's say you want to copy a simple variable . It's simple : ...

Random recommendation

  1. Python chart

    I saw a picture from a senior's blog , Turn around first , I'll look at it later

  2. Django REST framework Basics : Parsers and renderers

    Parser The role of the parser The function of the parser is that the server receives the data from the client , Parse data into data that you can process . The essence is to parse the data in the request body . Before you know the parser , We need to know first Accept as well as ContentTy ...

  3. KVM Installation and use

    1. The installation of the package 2. Creation and installation of virtual machine 3. Description of basic installation parameters 4. Common operations One . The installation of the package 1.#yum install -y kvm qemu-kvm libvirt virt-install brid ...

  4. tomcat The lack of tcnative-1.dll The solution of the ( Affirming : Source network )

    tomcat The lack of tcnative-1.dll The solution of the Address :http://blog.csdn.net/topwqp/article/details/7713388

  5. javascript Reading and writing files

    Integrate the Internet for js Implementation of the file read and write code , But this function can only be used in ie In the browser , And some of them on the computer ie Need to set up . Here's the write code : var fso = new ActiveXObject("Scr ...

  6. Mobile jq And zepto Event binding

    Recently, I've done mobile web pages , Yes zepto.js , Its general usage follows jquery almost , But I was trapped for a long time in the time binding . This is mainly about binding events to future elements . Elements of the future : This is through ajax The number of requests ...

  7. WP8.1 Learning Series ( Chapter 20 )—— Add controls and handle events

    precondition add controls Set the name of the control Set control properties Create an event handler New control summary On the topic By using buttons like . Text box and combo box control , You can create applications UI. How to add a control to an application is shown below . When working with controls , ...

  8. django Session tracking technology

    Catalog django Session tracking technology in What is session tracking technology HTTP Stateless protocol Cookie summary What is? cookie cookie Source code cookie For a long time cookie For a long time cookie Effective path Delete ...

  9. C++ Open source cross platform log Library glog Study and research ( One )

    As C++ One of the few good uses in the field . efficient . Cross platform logging tools ,Google Open source log library glog It's rare .glog It's a C++ Implementation of application level logging framework , Provides C++ Style stream operation . I happened to take advantage of May Day ...

  10. PHP Customize XML Class implements array to XML File conversion

    These two days in the company to write and search within the app store interface , Roughly like Baidu search within the application of such things , You can click the link below to see the details . Baidu search in app Some app stores need JSON Formatted data , So I just need to use the following statement to return to the other party's service ...