推理題,會則秒解

你和你的朋友,兩個人一起玩 Nim 游戲:桌子上有一堆石頭,每次你們輪流拿掉 1 - 3 塊石頭。 拿掉最后一塊石頭的人就是獲勝者。你作為先手。

你們是聰明人,每一步都是最優解。 編寫一個函數,來判斷你是否可以在給定石頭數量的情況下贏得游戲。

  • 示例:
輸入: 4
輸出: false 
解釋: 如果堆中有 4 塊石頭,那么你永遠不會贏得比賽;因為無論你拿走 1 塊、2 塊 還是 3 塊石頭,最后一塊石頭總是會被你的朋友拿走。

這道題是一道純推理題,最紅的結果是,如果剩余 n 為 4 的倍數,則,先手必輸,否則先手必贏。為什么呢?

其實很簡單,如果剩余 4,則無論先手如何取,剩余都會在 1-3 之間,后手可以一次取完,結局注定失敗!

所以,如果此時,剩余數量為 4 的倍數,則無論先手如何取,后手都可以控制每次遞減的數為 4。

而如果先手時,數量為 4n + k, 1 <= k <=3,則先手可以直接將 k 去掉,剩余 4n,后手在取石頭的時候,面臨的是 4n,則其必輸。

代碼如下

class Solution {
public:bool canWinNim(int n) {if (n % 4 == 0) {return false;} else {0return true;}}
};

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/375479.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/375479.shtml
英文地址,請注明出處:http://en.pswp.cn/news/375479.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

【圖論】割點、橋、雙連通

連通分量 個數可以通過一次BFS或者DFS得到 割點和橋 可以枚舉刪除每一個點或者每一條邊&#xff0c;判斷連通分量個數是否增加 更好的方法 該算法是R.Tarjan發明的。對圖深度優先搜索&#xff0c;定義DFS(u)為u在搜索樹&#xff08;以下簡稱為樹&#xff09;中被遍歷到的次序號…

奇酷手機顯示Log

1、在桌面點擊撥號&#xff0c;在撥號盤輸入“*20121220#”&#xff0c;進入工程模式;2、看到日志輸出等級&#xff0c;點進去 Log print enable 選 enable Java log level 選 LOGV C and C log level 選 LOGV Kernel log level 選 KERN_DEBUG3、完畢 參考網址&#xff1a;http…

getCanonicalPath getAbsolutePath區別

1、在winows環境下它們的區別是 &#xfeff;&#xfeff;getCanonicalPath是標準路徑&#xff0c;沒有特殊字符&#xff0c;getAbsolutePath是有特殊字符的 2、在AIX系統中它們的區別&#xff1a; 首先編譯&#xff1a;javac com/ai/test/BugTest.java 然后運行&#xff1a;ja…

Hbase與hive整合

//hive與hbase整合create table lectrure.hbase_lecture10(sname string, score int) stored by org.apache.hadoop.hive.hbase.HBaseStorageHandler whth serdeproperties("hbase.columns.mapping" :key,cf1:score)tblproperties("hbase.table.name" &q…

C++實現一個http服務器

一個簡單的博客后端服務器 github地址&#xff0c;持續更新 設計參考 #define MYSQLPP_MYSQL_HEADERS_BURIED #include "httplib.h" #include "rapidjson/document.h" #include <mysql/mysql.h> #include <iostream> #include <string>…

KMP算法的java實現

package com.trs.utils;public class KMPStr {/** 在KMP算法中&#xff0c;最難求的就是next函數&#xff0c;如何理解next函數是一個難題&#xff0c;特別是knext[k]&#xff0c;這里* 需要指出的是當p[i]!p[j]時&#xff0c;我們只有通過回溯將k的值逐漸減小&#xff0c;貌似…

線段分割法實現微信搶紅包

無意間看到的一種實現搶紅包的方法&#xff0c;于是用C實現了一下。 將一個紅包分成 n 份 具體的思路是&#xff0c;將一個紅包看作是一個線段&#xff0c;線段的長就是紅包總金額&#xff0c;然后在這個線段上隨機切 n-1 刀&#xff0c;分成 n 份&#xff0c;然后搶紅包的人依…

JAVA多線程和并發基礎面試問答(轉載)

JAVA多線程和并發基礎面試問答 原文鏈接&#xff1a;http://ifeve.com/java-multi-threading-concurrency-interview-questions-with-answers/ 多線程和并發問題是Java技術面試中面試官比較喜歡問的問題之一。在這里&#xff0c;從面試的角度列出了大部分重要的問題&#xff0c…

Linux的學習--crontab

之前了解過一點crontab&#xff0c;前段時間比較閑&#xff0c;就熟悉了一下&#xff0c;今天總結記錄一下。 crontab命令常見于Unix和類Unix的操作系統之中&#xff0c;用于設置周期性被執行的指令。該命令從標準輸入設備讀取指令&#xff0c;并將其存放于"crontab"…

C++雪花算法實現

看來一下雪花算法的實現方法&#xff0c;用 c試著實現了一下&#xff0c;這里僅僅是實現了算法的流程&#xff0c;但是具體的細節&#xff0c;如并發、多線程訪問等等沒有具體考慮。 雪花算法的簡單講解參考 #include <sys/select.h> #include <iostream> #includ…

CAlayer層的屬性

iOS開發UI篇—CAlayer層的屬性 一、position和anchorPoint 1.簡單介紹 CALayer有2個非常重要的屬性&#xff1a;position和anchorPoint property CGPoint position; 用來設置CALayer在父層中的位置 以父層的左上角為原點(0, 0) property CGPoint anchorPoint; 稱為“定位點”、…

Window Linux下實現指定目錄內文件變更的監控方法

轉自&#xff1a;http://qbaok.blog.163.com/blog/static/10129265201112302014782/ 對于監控指定目錄內文件變更&#xff0c;window 系統提供了兩個未公開API&#xff1a;SHChangeNotifyRegister SHChangeNotifyDeregister 分別用于注冊Notify以及監視。 同時&#xff0c;還提…

Odoo9發行說明

2015年10月1日&#xff0c;期待已久的Odoo9正式發布。本文是Odoo9正式版發行說明&#xff0c;基于官網資料翻譯。 譯者: 蘇州-微塵原文地址&#xff1a;https://www.odoo.com/page/odoo-9-release-notes譯文地址&#xff1a;http://blog.csdn.net/wangnan537/article/details/4…

揭秘史上最完美一步到位的搭建Andoriod開發環境

Windows環境下Android開發環境搭建雖然不難而且網上資料眾多&#xff0c;但是眾多資料如出一折 忽略了很多細節&#xff0c;最終還是沒能達到滿意效果。 基本步驟如下&#xff1a;JDK安裝、環境變量配置、Eclipse下載、AndoriodSDK下載安裝、下載配置ADT但是到這里還不算完美搞…

基于OpenCv的人臉檢測、識別系統學習制作筆記之二

在網上找到了一個博客&#xff0c;里面有大量內容適合初學者接觸和了解人臉檢測的博文&#xff0c;正好符合我目前的學習方面&#xff0c;故將鏈接放上來&#xff0c;后續將分類原博客的博文并加上學習筆記。 傳送門&#xff1a; http://blog.sina.com.cn/s/articlelist_160256…

URL 化

URL化。編寫一種方法&#xff0c;將字符串中的空格全部替換為%20。假定該字符串尾部有足夠的空間存放新增字符&#xff0c;并且知道字符串的“真實”長度。&#xff08;注&#xff1a;用Java實現的話&#xff0c;請使用字符數組實現&#xff0c;以便直接在數組上操作。&#xf…

第一章 00 StringUtil.cpp和StringUtil.hh分析

1 /*2 * StringUtil.hh3 *4 * Copyright 2002, Log4cpp Project. All rights reserved.5 *6 * See the COPYING file for the terms of usage and distribution.7 */8 頭文件的說明&#xff0c;以及與版權相關的說明一般都會放置在文件的開始位置 9 #ifndef _LOG4CPP_STR…

【SQL】服務器環境下的SQL

一、大型數據庫的三層體系結構 web服務器&#xff1a;比如在淘寶頁面上&#xff0c;輸入“牛肉干”&#xff0c;就是web服務器來處理&#xff0c;提交給應用服務器。 應用服務器&#xff1a;在獲取到“牛肉干”這個請求后&#xff0c;應用服務器決定如何匯集結果&#xff0c;并…

【置頂】全局變量的好處與壞處

近日在做項目的過程中對plsql的使用非常多&#xff0c;主要是編寫存儲過程實現業務邏輯。但是在coding的過程中遇到非常奇怪的問題。 問題是&#xff1a;在package包頭中定義了一個變量&#xff0c;current_time : sysdate,然后在procedure使用這個定義的變量&#xff0c;直接i…

三個線程按順序輸出數字

當 n 3N 時&#xff0c;線程1輸出 當 n 3N 1 時&#xff0c;線程2輸出 當 n 3N 2 時&#xff0c;線程3輸出 最終的輸出為 0、1、2、3、4、5、6、7、8、10 #include <iostream> #include <thread> #include <mutex> #include <condition_variable&g…