資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中將數字切割成多個部分，使得最大數量的部分能被3整除
在這個問題中，我們給定一個很大的整數（最多105位）。我們的任務是列印所需的總切割次數，使得被3整除的部分最多。
讓我們舉個例子來理解這個問題
輸入 − 9216
輸出 − 3
解釋 − 數字被分成 9|21|6。
為了解決這個問題，我們必須從數字的最低有效位開始，也就是數字的最後一位。在這裡，我們將找到最小的能被三整除的數字。然後根據它更新計數。
示例 − 如果arr[i]構成一個能被3整除的數字，那麼我們將增加計數並移動到數字的下一位。如果arr[i]不能被3整除，那麼我們將它與下一位組合起來，並檢查能否被3整除。
3的倍數 − 如果一個數字的各位數字之和能被三整除，則該數字能被三整除。
示例
程式演示我們解決方案的實現
#include <bits/stdc++.h>
using namespace std;
int countMaximum3DivisibleNumbers(string number){
int n = number.length();
vector<int> remIndex(3, -1);
remIndex[0] = 0;
vector<int> counter(n + 1);
int r = 0;
for (int i = 1; i <= n; i++) {
r = (r + number[i-1] - '0') % 3;
counter[i] = counter[i-1];
if (remIndex[r] != -1)
counter[i] = max(counter[i], counter[remIndex[r]] + 1);
remIndex[r] = i+1;
}
return counter[n];
}
int main() {
string number = "216873491";
cout<<"The number of 3 divisible number created by cutting "<<number<<" are : " <<countMaximum3DivisibleNumbers(number);
return 0;
}輸出
The number of 3 divisible number created by cutting 216873491 are : 5
更新於: 2020年4月17日
97 次瀏覽
廣告