Welcome to MDGSF's Blog!

This is my github blog

[C/C++] Generate random string

2016-06-06

C/C++

Rand

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <ctime>
#include <string.h>
#include "unistd.h"

using namespace std;

void vGenRandom(char * str, const int iLen);
void vGenAlphaCapital(char * str, const int iLen);
void vGenAlphaLower(char * str, const int iLen);
void vGenNumber(char * str, const int iLen);
void vHelp();

#define ALPHA_NUM 26
#define NUMBER_NUM 10
#define CHARACTER_NUM 32

char g_acAlphaCapital[ALPHA_NUM+1] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
char g_acAlphaLower[ALPHA_NUM+1] = "abcdefghijklmnopqrstuvwxyz";
char g_acNumber[NUMBER_NUM+1] = "0123456789";
char g_acCharacter[CHARACTER_NUM+1]= "!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~";


int main(int argc, char *argv[])
{
    srand(time(NULL));
    int iRet = 0;
    int iType = 0; //default type
    int iLength = 10; //default length
    int iNumber = 1; //default number

    while ((iRet = getopt(argc, argv, "t:l:n:h")) != -1)
    {
        switch(iRet)
        {
        case 't':
            iType = ::atoi(optarg);
            break;
        case 'l':
            iLength = ::atoi(optarg);
            break;
        case 'n':
            iNumber = ::atoi(optarg);
            break;
        case 'h':
            {
                vHelp();
                return 0;
            }
        default:
            printf("Unknown parameters\n");
            break;
        }
    }


    switch(iType)
    {
    case 0:
        {
            for (int i = 0; i < iNumber; i++)
            {
                char acRandom[BUFSIZ] = {0};
                vGenRandom(acRandom, iLength);
                printf("%s ", acRandom);
            }
        }
        break;
    case 1:
        {
            for (int i = 0; i < iNumber; i++)
            {
                char acRandom[BUFSIZ] = {0};
                vGenNumber(acRandom, iLength);
                printf("%s ", acRandom);
            }
        }
        break;
    case 2:
        {
            for (int i = 0; i < iNumber; i++)
            {
                char acRandom[BUFSIZ] = {0};
                vGenAlphaCapital(acRandom, iLength);
                printf("%s ", acRandom);
            }
        }
        break;
    case 3:
        {
            for (int i = 0; i < iNumber; i++)
            {
                char acRandom[BUFSIZ] = {0};
                vGenAlphaLower(acRandom, iLength);
                printf("%s ", acRandom);
            }
        }
        break;
    default:
        {
            printf("Unknown type: %d\n\n", iType);
            vHelp();
            return 0;
        }
    }
    printf("\n");

    return 0;
}

void vHelp()
{
    printf("Usage: genRandom [options] [target] ...\n");
    printf("Options:\n");
    printf("\t-t      type: (0:random, 1:number, 2:AlphaCapital, 3:AlphaLower)\n");
    printf("\t-l      length: the length of each obj\n");
    printf("\t-n      number: the number of random obj\n");
    printf("\t-h      help\n");
}

void vGenRandom(char * str, const int iLen)
{
    char acBuf[BUFSIZ] = {0};
    strcpy(acBuf, g_acAlphaCapital);
    strcat(acBuf, g_acAlphaLower);
    strcat(acBuf, g_acNumber);
    strcat(acBuf, g_acCharacter);

    int iBufLen = strlen(acBuf);
    //printf("acBuf len = %d\n", iBufLen);
    int i;
    for (i = 0; i < iLen; i++) {
        str[i] = acBuf[ rand() % iBufLen ];
    }
    str[i] = '\0';
}

void vGenAlphaCapital(char * str, const int iLen)
{
    int i;
    for (i = 0; i < iLen; i++) {
        str[i] = g_acAlphaCapital[ rand() % ALPHA_NUM ];
    }
    str[i] = '\0';
}

void vGenAlphaLower(char * str, const int iLen)
{
    int i;
    for (i = 0; i < iLen; i++) {
        str[i] = g_acAlphaLower[ rand() % ALPHA_NUM ];
    }
    str[i] = '\0';
}

void vGenNumber(char * str, const int iLen)
{
    int i;
    for (i = 0; i < iLen; i++) {
        str[i] = g_acNumber[ rand() % NUMBER_NUM ];
    }
    str[i] = '\0';
}

Read All

[转]0-1背包问题

2016-05-31

Art

终于看懂了，哈哈。感谢这位兄弟。

http://blog.csdn.net/dapengbusi/article/details/7463968

问题描述

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态可以取0和1.我们设物品i的装入状态为xi,xi∈ (0,1)，此问题称为0-1背包问题。

举例分析

数据：

物品个数n=5,

物品重量w[n]={0，2，2，6，5，4},

物品价值V[n]={0，6，3，5，4，6},

（第0位，置为0，不参与计算，只是便于与后面的下标进行统一，无特别用处，也可不这么处理。）

总重量c=10.

Ø背包的最大容量为10，那么在设置数组m大小时，可以设行列值为6和11，

那么，对于m(i,j)就表示可选物品为i…n背包容量为j(总重量)时背包中所放物品的最大价值。

31_01

31_02

31_03

31_04

31_05

31_06

31_07

31_08

31_09

31_10

31_11

31_12

31_13

31_14

31_15

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

int iMax(int a, int b) {
    return a > b ? a : b;
}


/*
 * @param iCapacity: the bag's capacity.
 * @param piWeight: the array of obj's weight.
 * @param piValue: the value of obj's value.
 * @param iObjNum: the number of objs.
 * @param [out]ppResult: the result.
 * @return the max value the bag can hold.
 */
int iBag(
    const int iCapacity,
    const int * piWeight,
    const int * piValue,
    const int iObjNum,
    int **ppResult)
{
    int i;
    int j;

    for (i = 0; i <= iCapacity; i++) {
        ppResult[iObjNum][i] = (i < piWeight[iObjNum]) ? 0 : piValue[iObjNum];
    }

    for (i = iObjNum-1; i >= 1; i--)
    {
        for (j = 0; j <= iCapacity; j++)
        {
            if (j < piWeight[i])
            {
                ppResult[i][j] = ppResult[i+1][j];
            }
            else
            {
                ppResult[i][j] = iMax(ppResult[i+1][j], piValue[i] + ppResult[i+1][j-piWeight[i]]);
            }
        }
    }

    return ppResult[1][iCapacity];
}

void answer(
    int iCapacity,
    const int n,
    const int w[],
    int **m,
    int x[])
{
    int j = iCapacity;
    int i;
    for (i = 1; i <= n-1; i++)
    {
        if(m[i][j] == m[i+1][j])
        {
            x[i] = 0;
        }
        else
        {
            x[i] = 1;
            j = j - w[i];
        }
    }
    x[n] = m[i][j] ? 1 : 0;
}

int main()
{
    int i,j;

    int c = 10;
    int w[] = {0, 2, 2, 6, 5, 4};
    int v[] = {0, 6, 3, 5, 4, 6};
    int n = sizeof(w)/sizeof(w[0]) - 1;

    int ** m = (int**)malloc(sizeof(int*)*6);
    for (i = 0; i < 6; i++) {
        m[i] = (int*)malloc(sizeof(int)*11);
    }

    int iResult = iBag(c, w, v, n, m);
    printf("iBag = %d\n", iResult);

    for (int i = 0; i <= 5; i++) {
        for (int j = 0; j <= 10; j++) {
            printf("%2d ", m[i][j]);
        }
        printf("\n");
    }


    int aiResult[100] = {0};
    answer(c, n, w, m, aiResult);
    for (int k = 1; k <= 5; k++)
    {
        printf("%d ", aiResult[k]);
    }
    printf("\n");
    return 0;
}

Read All

[C/C++] 线程加锁例子

2016-05-30

C/C++

    apr_thread_mutex_lock(m_pstMutex);
    apr_int32_t iMaxTryTime = m_oLBServerVector.size();
    apr_thread_mutex_unlock(m_pstMutex);
    while ( iMaxTryTime-- > 0 )
    {
        char acServerIPAddr[MAX_IPADDRESS_LENGTH] = {0};
        apr_uint32_t uiServerPort;

        apr_thread_mutex_lock(m_pstMutex);
        vector<SServerAddr>::iterator oLBIter = m_oLBServerVector.begin();
        strcpy(acServerIPAddr, oLBIter->m_acServerIPAddr);
        uiServerPort = oLBIter->m_uiServerPort;
        apr_thread_mutex_unlock(m_pstMutex);

        iRet = m_iQueryFromServerTCP(
                acServerIPAddr,
                uiServerPort,
                acSendMsgBuf,
                usSendMsgLen,
                acRecvMsgBuf,
                &usRecvMsgLen,
                &ucMsgType);
        if(APR_SUCCESS == iRet) {
            break;
        }

        apr_thread_mutex_lock(m_pstMutex);
        SServerAddr stServerAddr = *oLBIter;
        m_oLBServerVector.erase(oLBIter);
        m_oLBServerVector.push_back(stServerAddr);
        apr_thread_mutex_unlock(m_pstMutex);
    }
    if(iRet != APR_SUCCESS) {
        return iRet;
    }

(note:一个变量作为一个类的成员变量时，是多个线程共享的。作为临时变量，则是每个线程一份。)

这段代码的加锁有问题。问题：当两个线程都执行到 erase 的时候，vector被移动了两次。

解决方法一：把 m_iQueryFromServerTCP（）函数一起加锁，但是这样的话，锁太大，不建议采用。

解决方法二：在 erase 之前，先判断下当前的iter指向的是不是和之前取出来的一样。一样的话就移动，不一样的话就不移动。

解决方法三：把 iter 作为一个成员变量，这样就所有的线程都共享，在构造函数中初始化 iter = m_oLBServerVector.begin(); 然后每次都取出 iter 当前指向的值，失败的时候就把 iter 向后移动一格。（这种方法相当于是一个ring，所有线程共享一个指针。）

解决方法四：用一个ring，每个线程都有一个自己的移动指针。

解决方法三的代码如下：

    apr_thread_mutex_lock(m_pstMutex);
    apr_int32_t iMaxTryTime = m_oLBServerVector.size();
    apr_thread_mutex_unlock(m_pstMutex);
    while ( iMaxTryTime-- > 0 )
    {
        char acServerIPAddr[MAX_IPADDRESS_LENGTH] = {0};
        apr_uint32_t uiServerPort;

        apr_thread_mutex_lock(m_pstMutex);
        strcpy(acServerIPAddr, m_oLBIter->m_acServerIPAddr);
        uiServerPort = m_oLBIter->m_uiServerPort;
        apr_thread_mutex_unlock(m_pstMutex);

        iRet = m_iQueryFromServerTCP(
                acServerIPAddr,
                uiServerPort,
                acSendMsgBuf,
                usSendMsgLen,
                acRecvMsgBuf,
                &usRecvMsgLen,
                &ucMsgType);
        if(APR_SUCCESS == iRet) {
            break;
        }

        apr_thread_mutex_lock(m_pstMutex);
        if(strcmp(acServerIPAddr, m_oLBIter->m_acServerIPAddr) == 0 &&
           uiServerPort == m_oLBIter->m_uiServerPort)
        {
            m_oLBIter++;
            if(m_oLBIter == m_oLBServerVector.end()) {
                m_oLBIter = m_oLBServerVector.begin();
            }
        }
        apr_thread_mutex_unlock(m_pstMutex);
    }
    if(iRet != APR_SUCCESS) {
        return iRet;
    }

Read All

[C/C++] 代码检查

2016-05-27

C/C++

C Codechecking

写完代码检查流程

检查每个变量名是否合法，是否合理。

检查每个函数名是否合法，是否合理。(函数是一个操作，通常是 动词+名词)

检查类名是否合法，是否合理。(类名通常不应该出现动词)

malloc 是否有对应的 free。

new 是否有对应的 delete。

apr_thread_mutex_lock() 对应的 apr_thread_mutex_unlock() 不要写错了。

放在 for，while 循环中的临时变量申明 是否可以放到循环的外面。

循环体中的代码过长，考虑是否封装成一个函数替代。

失败的时候记得输出log，成功的关键路径上也要记得输入log。

对函数的输入参数进行合法性检查。

将类的成员变量初始化。

实现完一个函数，记得考虑是否需要多线程安全。

对指针操作前，先判断是否为NULL。

一个变量如果可以作为局部变量，就没有必要让它成为成员变量。

给类加上

private:
    CClass(const CClass&);
    CClass& operator = (const CClass&);

检查 if 和 while 中的 == 有没有写错了，写成了一个 = 。

Read All

[C/C++] sscanf basic usage

2016-05-24

C/C++

C Sscanf

#include <stdio.h>

#define MAC_LEN 6

int main()
{
    char acMac[] = "00:30:AB:2F:7F:EA";

    int aiMac[MAC_LEN] = {0};
    int iNum = sscanf(acMac, "%x:%x:%x:%x:%x:%x", &aiMac[0], &aiMac[1], &aiMac[2], &aiMac[3], &aiMac[4], &aiMac[5]);

    printf("iNum = %d\n", iNum);

    printf("%02x:%02x:%02x:%02x:%02x:%02x\n", aiMac[0], aiMac[1], aiMac[2], aiMac[3], aiMac[4], aiMac[5]);

    return 0;
}

Read All

[C/C++] 制表符的长度

2016-05-24

C/C++

C
制表符在界面上显示的长度不是固定的。

制表符表示的是，从行首开始，每8字节算一个制表位，’\t’会在当前内容结束后第一个空的制表位处接上下文。

我猜你是想对齐后面的数字，但是制表符没有强制对齐的功能的，这样的话你不得不数一数你两句话之间差了几个制表位了。
```
#include <stdio.h>
int main(int argc, char * argv[])
{
    printf("abcdefghijklmn\n");
    printf("\tabcd\n");
    printf("a\tbcd\n");
    printf("ab\tcd\n");
    printf("abcdefgh\tjklmn\n");
    return 0;
}
```
输出如下：
```
abcdefghijklmn
        abcd
a       bcd
ab      cd
abcdefgh        jklmn
```
Read All

82/97

Welcome to MDGSF's Blog!

[C/C++] Generate random string

[转]0-1背包问题

问题描述

举例分析

[C/C++] 线程加锁 例子

[C/C++] 代码检查

写完代码检查流程

[C/C++] sscanf basic usage

[C/C++] 制表符 的长度

[C/C++] 线程加锁例子

[C/C++] 制表符的长度