C++の組み合わせで適用されるstrtok文字列分割、配列分割アルゴリズム、動的配列関数パラメータ

4632 ワード

一、strtok文字列分割:
原型:char*strtok(char*str,const char*delim);
機能:文字列を1つの文字列に分解します.sは分解する文字列、delimは区切り文字列です.
説明:分解文字列は文字列のセットです.sは分解する文字列、delimは区切り文字列です.strtok()は、文字列を個々のセグメントに分割するために使用されます.パラメータsは分割しようとする文字列を指し、パラメータdelimは分割文字列に含まれるすべての文字である.strtok()がパラメータsの文字列にパラメータdelimに含まれる分割文字を発見すると、その文字は0文字に変更されます.最初の呼び出しではstrtok()にパラメータs文字列を与える必要があり、以降の呼び出しではパラメータsをNULLに設定します.呼び出しが成功するたびに、分割されたクリップへのポインタが返されます.
戻り値:sの先頭から分割された列.sの文字が末尾まで検索されると、NULLが返されます.delimの文字が見つからない場合は、現在のstrtokの文字列のポインタを返します.すべてのdelimに含まれる文字はフィルタされ、フィルタされた場所を分割ノードとして設定されます.
使用(c+):

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    char sentence[]="This is a sentence with 7 tokens";
    cout << "The string to be tokenized is:
" << sentence << "

The tokens are:

";
    char *tokenPtr=strtok(sentence,"");
    while(tokenPtr!=NULL)　{
        cout<<tokenPtr<<'
';
        tokenPtr=strtok(NULL,"");
    }
    //cout << "After strtok,sentence=" << tokenPtr<<endl;
    return 0;
}

関数の最初の呼び出しには、2つのパラメータを設定する必要があります.最初の分割の結果,列の最初の','の前の文字列,すなわち上のプログラムがabcを最初に出力することを返す.
この関数strtok(NULL,",")は2回目に呼び出され、最初のパラメータはNULLに設定されます.その結果、分割は、後の文字列、すなわち2回目の出力dに基づいて返される.
二、配列平分アルゴリズム
すなわち,配列を2つのグループに分け,この2つのグループのサブ配列の和の差の絶対値を最小にする.
構想:まず配列aのすべての要素をsumと求め、それから和の半分をxとし、それから配列aのすべてのサブセットを遍歴し、それぞれすべてのサブセットの要素の和sum(i)を求める.abs(x-sum(i))を比較し、小さくします.
実装(c+):

//      
int getMinTime(const vector<int>& arr){
    int n = arr.size();
    int sum = 0;
    for(int i=0;i<n;i++){
        sum += arr[i];
    }
    int minTime = sum,tmp = 0;
    for(int i=0;i<n;i++){
        tmp = 0;
        for(int j=i;j<n;j++){
           tmp += arr[j];
           //cout<<sum/2<<tmp<<" "<<minTime;
           if((tmp>(sum/2))&&(tmp<minTime)){
            minTime = tmp;
           }
        }
    }
    return minTime;
}

三、vector動的配列関数パラメータ
例:vectorarrが定義されている場合、関数呼び出しではたとえばこれはできません.

int func(int *arr){
    //...
}

正しい方法:

int func(const vector<int>& arr){
    //...
}

文字列配列についても同様です.

void func(const vector<string>& str){
    //...
}

2016年宜信校が募集したプログラミング筆記試験問題を添付します.
ホストと織姫は洗濯を罰され、最速の時間に洗濯しなければならない.いくつかの色と数量の服があって、彦星と織姫は同時に洗うことができて、全部で2つの洗濯板があって、2人は1つの色の服を洗った後でしか他の色の服を洗うことができなくて、しかもその中の1人が洗った後に別の人がこの色の最後の1枚を洗っていることに気づいたら、まずtaが洗ってから一緒に他の色の服を洗う必要があります.
input:
入力はいくつかの試験例を含み、第1行はm、nの2つの正の整数(m<10、n<100)がそれぞれ色と服の数を表す.2行目はmと色の文字列を含み、文字列の間にスペースが分かれ、次いでn行の文字列であり、各行の文字列はそれぞれ洗浄時間と色を記述し、洗浄時間は1000を超えず、同様に洗浄時間と色はスペースで分かれている.
output:
合計最小洗浄時間
入力例:

3 4
yellow red blue
2 yellow
3 red
4 red
6 blue

出力:

私の解答(c+):

#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

//           
int getIndex(const vector<string>& str,int n,string s){
    int index = 0;
    for(int i=0;i<n;i++){
        if(str[i]!=s){
            index++;
        }else{
            return index;
        }
    }
}

//      
int getMinTime(const vector<int>& arr){
    int n = arr.size();
    int sum = 0;
    for(int i=0;i<n;i++){
        sum += arr[i];
    }
    int minTime = sum,tmp = 0;
    for(int i=0;i<n;i++){
        tmp = 0;
        for(int j=i;j<n;j++){
           tmp += arr[j];
           //cout<<sum/2<<tmp<<" "<<minTime;
           if((tmp>(sum/2))&&(tmp<minTime)){
            minTime = tmp;
           }
        }
    }
    return minTime;
}

int main()
{
    int m,n;
    while(cin>>m>>n){
        vector <string> color(m);//         
        for(int i=0;i<m;i++){
            cin>>color[i];
        }
        vector <vector<int> > time(m,vector<int>(0));//        
        int t;
        string c;
        
        //          time    
        for(int i=0;i<n;i++){
            cin>>t>>c;
            int index = getIndex(color,n,c);
            time[index].push_back(t);
        }
        
        int tmp = 0;
        for(int i=0;i<m;i++){
            tmp += getMinTime(time[i]);//           
        }
        cout<<tmp<<endl;
    }
    
    return 0;
}

c++学習11

protobufのC++実装でChainerのCaffeモデルの読み込みを10倍早くする