從周三課開始總算輕鬆了點，下午能在宿舍研究點題目啥的打一打，還好，剛開學的課程還算跟得上，剛開學的這些課程也是複習以前學過的知識，下半學期也不敢太划水了，被各種人寄予厚望之後瑟瑟發抖，只能努力前行了~自己好多地方還做得不夠好，真的是要提升的方面太多了，加油吧~

今日興趣新聞：

網易回應裁員：公司確實正在進行結構性優化

鏈接：https://baijiahao.baidu.com/s?id=1626619207432301200&wfr=spider&for=pc

偶爾反新聞經常看到這些大公司的裁員，谷歌、微軟、華為、百度都出現過大幅度的裁員，現在網易也開始了，這會不會加劇了未來畢業職業出口的緊張呢？

------------------------------------------------題目----------------------------------------------------------

Gizilch

Problem Description

Input

Output

Sample Input

343 49
3599 610
62 36

Sample Output

49 
610 
62

------------------------------------------------題目----------------------------------------------------------

（一） 原題大意：

　　　　原意說的是有一到一百個葡萄，有兩個人去吃這些葡萄，每個葡萄上面有數字，每個人吃到的葡萄乘積之和就是自己的答案，獲得最大的數就是勝利，但有人為了勝利會假報自己的數字，讓你去識破他。

　　　　簡單來說，就是一個游戲：

　　　　有兩個人玩游戲A、B人，A和B都報一個數，其中最大的人是被挑戰者，最小的那個人是挑戰者，然後兩人的數通過因式分解，若挑戰者中總存在一種分解，是被挑戰者總有的因數，那麼說明被挑戰者說謊，判挑戰者勝利。

　　　　舉例：

　　　　A = 343 B = 49 顯然A>B，那麼A是被挑戰者，B是挑戰者，正常來說較小的人不說假話，因為如果他要說假話為何不往大的數說呢，好讓自己贏。

　　　　所以對A、B進行因式分解，對於B來說，你只能吃49才能得到，所以A不能再使用49了，但是A可以因式分解成49 * 7，所以可以看得出來A說了假話，判B勝利~

（二） 題目分析：

　　　　這道題有點小難度對於新手的我來說，查閱了一些解法加之自己的理解，是需要用到遞歸的DFS深搜方法去實現的。

　　　　首先建立一個數組，用來存儲100個葡萄，value為0則說明還沒被吃，1說明已經吃過不能再吃了，通過這種方法來判斷A、B是否有因數重覆。

　　　　然後對挑戰者進行因式分解，得到挑戰者的因式分解，然後再對被挑戰者進行因式分解，如果被挑戰者能夠順利的因式分解，那麼被挑戰者獲勝，否則挑戰者獲勝。

　　　　後面我會簡單整理一下深搜筆記~

（三） 代碼分塊：

　　　　第一步：分清挑戰者和被挑戰者：

        if(a>b)
        {
            attacker = b;
            victim = a;
        }
        else
        {
            attacker = a;
            victim = b;
        }

　　　　第二步：對挑戰者進行因式分解：

result_dfs = dfs(attacker);

　　　　這裡需要自己定義dfs深搜函數，那麼下麵開始定義深搜dfs：

　　　　第三步：dfs函數構造：分解因式：

    if(number > 100) size = 100;
    else size = number;
    
    for(i = 2 ; i<= size ; i++)
    {
        if( number %i == 0 && already[i] == 0)
        {
            already[i] = 1;
            if(dfs( number / i ) == 1) return 1;
            already[i] = 0;
        }
    }

　　　　第四步：dfs函數構造：判斷挑戰者和被挑戰者的因式分解情況：

    if(number == 1)
    {
        if(vic_divided == 0)
        {
            vic_divided = 1;
            vic_divide = 1;
            if(dfs(victim) == 1) return 1;
            else{
                vic_divided = 0;
                return 0;
            }
        }
        return 1;
    }

　　　　第五步，根據dfs返回的結果判斷勝負：

        if(vic_divided == 1 && result_dfs == 1 || vic_divide == 0)    winner = victim;
        else winner = attacker;

（四） AC代碼：

#include<stdio.h>
#include<string.h>

int attacker,victim;
int vic_divided,vic_divide;
int already[101];


int dfs(int number)
{
    int i,size;
    
    if(number == 1)
    {
        if(vic_divided == 0)
        {
            vic_divided = 1;
            vic_divide = 1;
            if(dfs(victim) == 1) return 1;
            else{
                vic_divided = 0;
                return 0;
            }
        }
        return 1;
    }
    
    if(number > 100) size = 100;
    else size = number;
    
    for(i = 2 ; i<= size ; i++)
    {
        if( number %i == 0 && already[i] == 0)
        {
            already[i] = 1;
            if(dfs( number / i ) == 1) return 1;
            already[i] = 0;
        }
    }
    return 0;
}

int main()
{
    int a,b,result_dfs,winner;
    while(scanf("%d %d",&a,&b) != EOF)
    {
        vic_divide = vic_divided = 0;
        memset(already, 0, sizeof(already));
        if(a>b)
        {
            attacker = b;
            victim = a;
        }
        else
        {
            attacker = a;
            victim = b;
        }
        
        result_dfs = dfs(attacker);
        
        if(vic_divided == 1 && result_dfs == 1 || vic_divide == 0)    winner = victim;
        else winner = attacker;
        
        printf("%d\n",winner);
    }
    return 0;
 } 

（五）AC截圖：

（六） 解後分析：

　　　　這道題用到了深搜，即深度優先搜索，簡稱DFS，對應的還有BFS，廣度優先搜索。

　　　　事實上，深度優先搜索屬於圖演算法的一種，英文縮寫為DFS即Depth First Search.其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次。

 　　　　如果我們從A點發起深度優先搜索（以下的訪問次序並不是唯一的，第二個點既可以是B也可以是C,D），則我們可能得到如下的一個訪問過程：A->B->E（沒有路了！回到A)->C->F->H->G->D（沒有路，最終回到A,A也沒有未訪問的相鄰節點，本次搜索結束）

 　　　　參考：https://baike.baidu.com/item/深度優先搜索/5224976

　　　　做了幾道題之後，簡單悟到一些使用BFS、DFS的一些方式，但還很淺顯，需要加強題量練習提升自己：

　　　　=》BFS是用來搜索最短徑路的解是比較合適的，比如求最少步數的解，最少交換次數的解。

　　　　=》DFS不需要保存搜索過程中的狀態，而BFS在搜索過程中需要保存搜索過的狀態，而且一般情況需要一個隊列來記錄。

　　　　=》DFS適合搜索全部的解，因為要搜索全部的解，那麼BFS搜索過程中，遇到離根最近的解，並沒有什麼用，也必須遍歷完整棵搜索樹，DFS搜索也會搜索全部，但是相比DFS不用記錄過多信息，所以搜素全部解的問題，DFS顯然更加合適。

註：我還是個渣渣輝，代碼可能寫得不夠高效不夠好，我也會努力優化，如果有更好的解法，真心希望您能夠評論留言貼上您的代碼呢~互相幫助互相鼓勵才能成長鴨~~